백준, BOJ, 2156번 C++ [CPP]

포도주시식이란다.

이것도 역시 다이나믹 프로그래밍이다.

근데

이 문제도 감이 올 듯 안온다.

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

---

 

우선 풀이를 보자

#include<iostream>
#include<algorithm>

using namespace std;

int drink[10001];
int dp[100001];
int N;

int main(){
    cin >> N;
    
    for(int i = 1; i<=N; i++){
        cin >> drink[i]; 
    }
    dp[1] = drink[1];
    dp[2] = drink[1] + drink[2];
    
    for(int i = 3; i<=N; i++){
        dp[i] = max(dp[i-1],max(dp[i-3]+drink[i-1]+drink[i],dp[i-2]+drink[i]));
    }
    
    cout << dp[N];
    
}

 

3잔 연속으로 마실 수 없다.

최댓값을 구해라.

문제 핵심이다.

 

3잔 연속으로 마실 수 없기에

3잔이상을 마실 때에는 골라 마셔야 한다는 것을 직감적으로 느낀다.

1잔 - 당연히 마신다.

2잔 - 당연히 마신다.

3잔 - 골라서 마셔야 한다.

 

즉, 어떻게 골라야 최댓값이 나오느냐? 를 프로그래밍 해야 한다.

 

3잔이 나오는 경우 마실 수 있는 방법은..?

OOO랑 XXX는 당연히 아닐테고

OXO, OOX, XOO 밖에 없을 것이다. 무조건 먹어야 최댓값이 나올테니까..?

 

이걸 통과하는 핵심이 있다.

앞에 최댓값은 뒤에 값이 입력이 되더라도 최댓값이다.

즉, dp[3]은 3개가 들어왔을 때 최댓값이 들어간다.

 

??무슨 말이냐??

 

즉, 다이나믹 프로그래밍을 풀 때 앞의 결과를 이용해야 한다는 소리다.

즉, 마지막 세부분들 두고 보았을 때

dp[i-3] + 위 3개 조합중 가장 큰 것이 답이라는 말이다.

그래서 위와 같이 안풀고 아래같이 바꾸어서 풀어도 된다라고 생각했다.

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

..그래서 틀렸다.

 

왜냐하면 위의 식은 dp[i-3]이 어떻게 끝나는 지를 모른다.

dp[i-3]이 마지막 잔이 마셨다면 OOX는 당연히 안되는 식이다.

 

그렇기 때문에

 

dp[i-3] XOO

dp[i-2] XO

dp[i-1]X

가 되는 것이다.

 

헷갈린다.

처음부터 잘하는 사람이 있겠냐마는..아무튼 다이나믹 프로그래밍 재밌으면서 뭔가 어렵다.