[백준 2156] 포도주 시식

문제

링크

풀이

정의

W[N] : N번째 포도주의 양
D[N] : N번째에서 최대로 마실 수 있는 포도주 양
ex) D[1] : 1번쨰에서 최대로 마실 수 있는 포도주의 양은 6이다

index	0	1	2	3	4	5	6
W[N]	0	6	10	13	9	8	1

처음부터 한번 수식을 세워보자!
D[0] 일 때 : 0
D[1] 일 때 : 1잔을 마시는게 최대값 즉, W[1]
D[2] 일 때 : 2잔을 모두 마시는게 최대값 즉, W[1] + W[2]
D[3] 일 때 : 총 3가지의 경우의 수가 있다.

1. 안마시는 경우, 이땐 D[2]가 최대값이 된다
   
2. 연속 1잔만 마시는 경우, 이전에 마시면 연속 2잔이 되기 때문에 이때는 W[1] + W[3]
   
3. 연속 2잔 마시는 경우, 이전전에선 마시면 안된다! W[2] + W[3] + W[0]
   

이제 조금 정리를 해보자.
연속 1잔만 마시는 경우 : W[1]+W[3] -> D[1] + W[3]과 같다
연속 2잔 마시는 경우 : W[2] + W[3] + D[0]과 같다
즉, D[3]일 때 3가지 경우의 수식은

1. D[3] = D[2]
2. D[3] = D[1] + W[3]
3. D[3] = W[2] + W[3] + D[0]

이 3가지 경우의 수 중 최대값을 구하면된다.
코드로 짤수 있도록 [숫자]를 n으로 변경해보자
예를 들어 D[3] = D[n] 이면, D[2]는 3-1 = 2이므로 D[n - 1]이 된다

1. D[n] = D[n - 1]
2. D[n] = D[n-2] + W[n]
3. D[n] = W[n -1] + W[n] + D[n - 3]

이제 이 수식을 이용해 코드를 짜보자!

코드

func solve(n: Int){
    var wines = [Int](repeating: 0, count: n + 1)
    var dp = wines
    
    for i in 1 ... n {
        wines[i] = Int(readLine()!)!
    }
    
    if n == 1 {
        print(wines[1])
        return 
    }else if n == 2 {
        print(wines[1] + wines[2])
        return
    }
    dp[1] = wines[1]
    dp[2] = wines[1] + wines[2]
    
    for i in 3 ... n {
        var maxWines = dp[i - 1] // 0 잔 마실 때
        maxWines = max(maxWines, dp[i - 2] + wines[i]) // 1잔 마실때 vs 0잔 마실 때 최대값 비교
        dp[i] = max(maxWines, dp[i - 3] + wines[i] + wines[i - 1]) // 2잔 마실 때와 위의 결과값 비교
    }
    
    print(dp[n])
}