문제 설명

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오.

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

입력

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1 ≤ n ≤ 10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

출력

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.

문제 풀이

굉장히 당황스러운 문제였다. 문제의 조건 중 하나인 ‘연속해서 3잔을 마실 수 없다’와 마신 포도주의 최대값을 구하는 문제, 어디서 많이 본 것 같지 않은가?
바로 ‘계단 오르기’ 문제를 떠올린 필자는 그때의 코드를 기억대로 쭉 써서 제출했지만 틀리고 말았다. 분명 틀린 점이 없었는데 왜 틀린 것인가 알 수 없었지만 이 문제는 ‘계단 오르기’ 문제와는 결정적인 차이점이 하나 있었다. 바로 ‘몇 칸을 건너뛰든 상관 없다’는 점이다.
이전의 ‘계단 오르기’의 코드는 우리는 i번째 계단을 연속되지 않는 첫 계단으로 밟는다면, 우리는 i-2번째 계단을 무조건 밟는다는 가정 하에 성립하는 코드이다.
하지만 이 ‘포도주 시식’에서는 i-3번째를 마시고 죽 건너뛰어서 i번째 잔을 시음할 수도 있는 것이다. 그에 맞게 코드를 수정해서 통과할 수 있었다. 비슷한 문제라고 바로 갖다써선 안된다는 소중한 교훈을 얻을 수 있었다.

코드

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    int n; cin >> n;
    int  table[10005];
    for(int i=0; i<n; i++) {
        cin >> table[i];
    }
    int dp[10005][2]={0,};//첫 계단일 때가 0, 두번째로 밟았다면 1
    if(n==1) {
        cout << table[0]; return 0;
    }
    dp[0][0]=table[0]; dp[0][1]=table[0];
    dp[1][0]=table[1]; dp[1][1]=table[0]+table[1];
    for(int i=2; i<n; i++) {
        for(int j=i-2; j>=0; j--) {
            dp[i][0]=max(max(dp[j][0]+table[i],dp[j][1]+table[i]),dp[i][0]);
        }//계단오르기와 달리 몇칸이든 건너뛸 수 있으므로 이전 값들중
        //가장 큰 값을 구해준다.
        dp[i][1]=dp[i-1][0]+table[i];
    }
    int maxi=0;
    for(int i=0; i<n; i++) {
        if(dp[i][0]>maxi) maxi=dp[i][0];
        if(dp[i][1]>maxi) maxi=dp[i][1];
    }//최대값을 구해준다.
    cout << maxi;
}