[백준/C++/Silver(1)] 2156 - 포도주 마시기

2156번: 포도주 시식

본인이 해당 문제의 출제자가 아니며, 문제 자체에 대한 모든 사항은 위의 링크가 출처임을 명시합니다.

 

아직도 몇 잔 못 마셔 봤다고!

 한 줄로 놓인 포도주잔을 원하는 대로 시음할 수 있다면 기분 좋을 것 같다. 놀랍게도 여기 있는 사람은 그냥 많이 먹는 게 목적인 것 같지만. 시식회라는 게 진짜 있는 건가? 난 모르겠다.

문제 : 

 간단히 하자면 이렇다.

 첫째 줄에 포도잔의 개수 n이 1~10000 사이의 정수로 주어지고 그 이후로는 포도잔에 담긴 포도주의 양이 적혀있다. 연속으로 놓여있는 3잔을 모두 마실 수는 없다고 할 때, 최대로 포도주를 먹을 수 있는 양은?

생각 :  

 문제를 딱 읽으니까 dp문제라는 생각이 들었다. 2차원이든, 1차원이든 뭔가의 최대 / 최솟값을 조건 있어 구하라고 하면 대부분은 이런 문제 유형인 듯하다. 일단 1일 차에는 이 문제를 푸는 걸 실패했는데, 코드는 이렇다.

코드 1 (dp 2중 배열 사용, 실패) : 

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int map[10005] = {0};
    int dp[10005][3] = {0};
    
    int n;
    cin >> n;
    
    for(int i = 0; i < n; i++){
        cin >> map[i];
    }
    
    dp[0][0] = map[0];
    dp[0][1] = map[0];
    //cout << "dp 00: " << dp[0][0] << '\n';
    //cout << "dp 01: " << dp[0][1] << '\n';

    dp[1][0] = map[1];
    dp[1][1] = map[0] + map[1];
    //cout << "dp 10: " << dp[1][0] << '\n';
    //cout << "dp 11: " << dp[1][1] << '\n';

    dp[2][0] = map[0] + map[2];
    dp[2][1] = map[1] + map[2];
    //cout << "dp 20: " << dp[2][0] << '\n';
    //cout << "dp 21: " << dp[2][1] << '\n';
    
    for(int i = 3; i < n; i++){
        dp[i][0] = max(dp[i - 2][1] + map[i], max(dp[i - 3][0], dp[i - 3][1]) + map[i]);
        //cout << "dp " << i << "0: " << dp[i][0] << '\n';
        dp[i][1] = max(dp[i - 1][0] + map[i], max(dp[i - 3][0], dp[i - 3][1]) + map[i] + map[i - 1]);
        //cout << "dp " << i << "1: " << dp[i][1] << '\n';
    }
    
    int check = (n > 1 ? (int)max(dp[n - 2][0], dp[n - 2][1]) : 0);
    //int check = 0;
    
    cout << max(dp[n - 1][0], max(dp[n - 1][1], check));
    
    return 0;
}

 dp의 꽃이라고 하면 점화식일 것이다. 나는 일단 i번째 포도잔까지 마셨을 때, 마실 수 있는 최댓값을 dp 배열에 넣어서 생각을 하려고 했다. 다만, 마지막 잔을 마셨는지, 그 이전 잔을 마셨는지, 도통 알 수가 없었기 때문에 이를 이중 배열로 만들어서 정보를 저장해 가면서 풀었다.

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

//dp[i][0] = i번째 포도주잔 까지 마셨을때 최댓값, 단 마지막 잔은 마셨으며 그 직전 잔은 마시지 않았음.
//dp[i][1] = i번째 포도주잔 까지 마셨을때 최댓값, 단 마지막 잔은 마셨으며 그 직전 잔도 마셨음.

 포도주의 양의 음의 정수이지는 않기 때문에 가능한 대로 마시는 것이 좋아서 위의 점화식을 쓰면 된다고 생각했다. 하지만 이 코드는 정답이 아니었다. 어떤 이유에서인지, 2%도 넘기지 못한 채로 틀렸다. 경곗값 테스트나 예제도 넣어봤는데 정답이 나와서 뭐가 문제인지를 도통 알아내지를 못했다. 하지만 시간이 늦었기 때문에 다음날에 이어서 풀어보기로 했다.

 

 다음날이 되어서 든 생각은 일단 알고리즘을 갈아 엎어야 겠다는 생각이었다. 일단 dp 치고 점화식이 너무 복잡한 것도 있었고, 이중 배열 말고 하나로 줄여서 생각을 해보고 싶었다. 

코드 2 (성공) :

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int map[10005] = {0};
    int dp[10005] = {0};
    
    int n;
    cin >> n;
    
    for(int i = 0; i < n; i++){
        cin >> map[i];
    }
    
    dp[0] = map[0];
    dp[1] = map[0] + map[1];
    dp[2] = max(map[0] + map[2], max(dp[1], map[1] + map[2]));
    
    for(int i = 3; i < n; i++){
        dp[i] = max(dp[i - 2] + map[i], 
            max(dp[i - 1], dp[i - 3] + map[i - 1] + map[i]));
    }
    
    cout << dp[n - 1];
    
    return 0;
}

 다행히도 그 다음 시도에서 맞을 수 있었다. 사실은 dp [2]를 계산하고 싶어서 어떻게 하는 게 좋을까 하다가 나온 게 위의 dp [2] 계산식인데, 이를 조금만 변형하면 되지 않을까 싶었다.

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

이게 말이 되는 이유는 단순히 일단 dp [i]까지 계산을 마지막 잔을 마셨는지, 마시지 않았는지 모르기 때문에 일단 마셨다고 가정하고 안전한 코드를 짰기 때문이다.

1. 이전잔을 마시고(마시지 않았을지도?) 이번잔을 마시지 않음

= dp[i - 1] + 0

2. 2번째 이전잔을 마시고(마시지 않았을지도?), 이전잔을 확실히 마시지 않고, 이번잔을 마심

= dp[i - 2] + map [i]

3. 3번째 이전잔을 마시고(마시지 않았을지도?), 2번째 이전잔을 확실히 마시지 않고, 이전잔과 이번잔을 마심

= dp [i - 3] + map [i - 1] + map [i])

 

 이런 식으로 계산을 한 다음 이 중에서 제일 큰 값을 찾아서 dp [i]에 넣어주었다.

 

 다행히도 시간을 들이면 무슨 문제든 풀리기는 하나보다. Silver 1 ~ Gold 5 문제 중에서 푼 사람이 많은 문제들을 많이 풀어봐야겠다.