[백준] (Swift) 2156번 - 포도주 시식 (dp, 스위프트 다이나믹 프로그래밍 풀이)

문제 링크

https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

 

나의 풀이

먼저 규칙을 찾는데 시간이 조금 걸렷다. 과연 이렇게 푸는게 앞에꺼가 세개 반복되지 않고 구하는게 맞나? 싶었던 의심이 들었었다. 하지만 점화식을 생성하면서, 두번 연속 나온건 제외하고 점화식을 세워주면 되는 거였다. (이게무슨말이지,, 말로표현이 안되네 ㅠㅠ) 어쨋든 풀이는 아래와 같다.

예시로 준것 처럼, 포도주가 6개 주어졌따면, 위와 같이 구할 수 있다. 최대가 될 수 있는 경우의 수를 보고 아래와 같은 점화식을 구할 수 있다. dp는 최대로 가질 수 있는 값 (표에서 4행)을 넣어준 배열이다.

dp[5] 는 위의 경우의 수에서 최대 값을 구해 넣어주면 된다. 이것을 max() 함수를 활용하여 구해주면 아래와 같다.

 

소스 코드 - 맞았습니다!

• n 은 입력받을 포도주의 개수
• podoju 는 입력받은 포도주의 양
• dp 는 podoju[i] i 번째 포도주까지 마셨을때의 최대 값을 넣어준 배열
• n>1, n>2 조건을 꼭 넣어주어야 한다. 만약 n=1 이라면, n>2 안에있는 점화식을 통과할 필요도 없고, range of index 에러가 발생한다. 

let n = Int(readLine()!)!
var podoju: [Int] = []
var dp = Array(repeating: 0, count: n+1)
podoju.append(0)

for _ in 1...n {
    podoju.append(Int(readLine()!)!)
}

dp[1] = podoju[1]

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

if n > 2{
    for i in 3..<n+1 {
        dp[i] = max(dp[i-1], dp[i-3] + podoju[i-1] + podoju[i], dp[i-2] + podoju[i])
    }
}

print(dp[n])