[Swift][DP] 백준 2156번 (포도주 시식)

요구능력 : DP에 대한 이해

 

코드설명 : 

 

문제의 핵심은 3잔연속으로 선택하면 안된다는점과 가장 많은양의 포도주를 마셔야한다는점이다.

보통 이렇게 숫자가 나열되어있고 가장많은양의~, ~~연속 이런식으로 나오면 DP의 2가지 요소가 충족해서 DP로 풀면된다.

 

6 10 13 9 8 1이 있다.

어차피 첫번째 dp의 최대값은 주어진 배열의 맨앞의 수이다.

쌓일 수 있는 값이 없기때문이다.

dp[1] = arr[1]

마찬가지로 dp[2]도 3잔연속되는 경우가 없기에

dp[2] = arr[2]이다.

 

그럼 이제, dp[3]을 구해보자.

dp[3]은 세번째 잔이기 때문에 문제의 조건을 다뤄줘야한다.

악필..

이렇게 세가지 경우의 수중 최댓값을 찾으면 그게 점화식의 완성이다.

점화식은 아래 코드에 적혀있습니다.

 

 

후기 : 규칙은 다찾았는데 왜자꾸 큰수가 나오나 싶엇더니 dp랑 arr을 잘못섞어쓰다가 시간이 걸렸다..

let n = Int(String(readLine()!))!
var arr:[Int] = []
var dp = Array(repeating: 0, count: 10001)
arr.append(0)
for _ in 1...n {
    arr.append(Int(String(readLine()!))!)
}

dp[1] = arr[1]
if n >= 2 {
    dp[2] = arr[1] + arr[2]
}

for i in stride(from: 3, through: n, by: 1) {
    dp[i] = max(dp[i - 2] + arr[i], dp[i - 3] + arr[i] + arr[i - 1], dp[i - 1])
}

print(dp[n])