[BOJ] 포도주 시식 / Dynamic programming

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

2156번: 포도주 시식

 

C++ 풀이 코드

#include <iostream>
#include <algorithm>
#define MAX_N (10000)
using namespace std;

int N;
int wines[MAX_N + 1];
int dp[MAX_N + 1];
int answer;

void solve() {
    cin >> N;

    for (int i = 1; i <= N; ++i) {
        cin >> wines[i];
    }

    if (N == 1) {
        cout << wines[1];
        return;
    }
    
    dp[0] = 0;
    dp[1] = wines[1];
    dp[2] = dp[1] + wines[2];
    answer = max(dp[1], dp[2]);

    for (int i = 3; i <= N; ++i) {
        dp[i] = max(max(dp[i -2], dp[i-3] + wines[i-1]) + wines[i], dp[i-1]);
        answer = max(answer, dp[i]);
    }

    cout << answer;
}

int main() {
    solve();
    return 0;
}

 

점화식을 세웠는데 처음에 잘못 짜서 계속 틀렸다.

dp[i] = max(max(dp[i -2], dp[i-3] + wines[i-1]) + wines[i], dp[i-1]); //옳은 점화식

dp[i] = max(dp[i -2], dp[i-3] + wines[i-1])  + wines[i]; //틀린 점화식

 

 

점화식을 짤 때 ...

 

dp[i] = i 번째 포도주를 '마실 때' 마실 수 있는 포도주의 양

 

...으로 생각했다. 그래서 전전(=i-2)번째 포도주를 '마실 때' 최대값과 전전전(=i-3)번째 와인을 '마실 때' 최대값에 직전 포도주의 양을 더한 값을 비교하여 큰 값을 선택했다. 이를 다음과 같이 작성했다.

max(dp[i -2], dp[i-3] + wines[i-1])

 

 

하지만 이렇게 생각하면 틀렸다. 왜냐하면 i 번째 포도주를 마시지 않을 때 최대로 마시는 경우가 있기 때문이다.

 

예를 들어

100 100 1 1 100 100 에 대하여

 

100	100	1	1	100	100
O	O	X	X	O	O

(O는 마시는 포도주, X는 안마심)

 

위와같을 때 최대로 마시게 된다. 하지만 잘못된 점화식에 따르면

0 = dp[0]	100	100	1	1	100	100
	100	200
i = 3			101
i = 4				201
i = 5					301
i = 6						301

 

위와같이 DP 테이블이 갱신된다.

이는 잘못된 것이다.

 

i번째 포도주를 포기하는 대신 i-2, i-1 번째 포도주를 전부 마실때 최대가 될 수 있기 때문이다. 

즉, dp[i-1]을 고려 대상에 포함시켜 다음과 같은 점화식으로 계산해야 한다.

dp[i] = max(max(dp[i -2], dp[i-3] + wines[i-1]) + wines[i], dp[i-1]);

0 = dp[0]	100	100	1	1	100	100
	100	200
i = 3			200
i = 4				201
i = 5					301
i = 6						400