백준 2156 포도주 시식
23 Jun 2021https://www.acmicpc.net/problem/2156
포도주가 순서대로 주어질 때 연속으로 놓여 있는 3잔을 모두 마실 수 없다고 했을 때 포도주를 가장 많이 먹는 방법을 구하는 문제이다. 점화식을 세워보면 다음과 같다.
dp[i][0] = max(dp[i-1][0], dp[i-1][1])
dp[i][1] = max(dp[i-1][0], dp[i-2][0] + c[i-1]) + c[i]
여기서 c는 포도주의 양을 순서대로 나열해놓은 배열이다. 현재 포도주를 마시지 않을 경우는 이전 포도주를 마신 것과 안마신 것중에서 최댓값이 올 것이고 현재 포도주를 마실 경우에는 3개를 연속해서 마실 수 없기 때문에 이전꺼를 안마실경우와 전전꺼를 안마시고 이전꺼를 마신경우 2가지 경우로 나눠서 최댓값을 찾아준다.
- DP code
var dp = Array(repeating: Array(repeating: 0, count: 2), count: 2)
dp[0][1] = c[0]
dp[1][0] = c[0]
dp[1][1] = c[0]+c[1]
for i in 2..<n {
let nDrink = max(dp[1][0], dp[1][1])
let Drink = max(dp[1][0], dp[0][0] + c[i-1]) + c[i]
dp[0] = dp[1]
dp[1] = [nDrink, Drink]
}
print(max(dp[1][0], dp[1][1]))
이 때 앞에서와 마찬가지로 전전꺼까지의 결과만 있으면 되기 때문에 dp 배열을 2x2로 표현하여 불필요한 메모리 사용을 줄여주었다.
- 전체 코드
let n = Int(readLine()!)!
var c = Array(repeating: 0, count: n)
for i in 0..<n {
c[i] = Int(readLine()!)!
}
if n == 1 {
print(c[0])
}
else {
var dp = Array(repeating: Array(repeating: 0, count: 2), count: 2)
dp[0][1] = c[0]
dp[1][0] = c[0]
dp[1][1] = c[0]+c[1]
for i in 2..<n {
let nDrink = max(dp[1][0], dp[1][1])
let Drink = max(dp[1][0], dp[0][0] + c[i-1]) + c[i]
dp[0] = dp[1]
dp[1] = [nDrink, Drink]
}
print(max(dp[1][0], dp[1][1]))
}