알고리즘 - 백준 2156 (포도주 시식)

문제 링크: https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

 

---

 

문제

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

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

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

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

 

입력

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

 

출력

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

 

---

 

풀이 및 코드

그래도 dp 문제 몇 개 풀다보니까 점점 문제 푸는 감을 익혀가는 것 같아서 기분은 좋다 ㅎ

다른 문제처럼 이 문제도 dp 표를 그려가면서 어떻게 하면 이전에 구한 값들을 사용할 수 있을까에 대한 고민을 많이 했고, 내가 생각한 풀이는 다음과 같다.

먼저, 앞에서부터 결과값을 구하고, 해당 결과값으로부터 뒤의 결과값들을 구하면서 dp 테이블을 채워나가는 식으로 구현하였다. 이를 위한 일반화된 식을 구하기 위해 먼저 가장 간단한 경우부터 생각해보았다.

현재 결과값을 구할 때 가장 간단한 경우는 앞선 세 개 중 이미 두 개를 먹지 않았을 경우이다.이 경우에는 당연히 앞 최댓값에 현재 포도주도 마실 수 있으므로 

dp[i] = dp[i - 1] + input[i]

식을 구할 수 있다.

 

해당 식을 디폴트로 두고, 이제부터는 앞선 세 포도주 중 이미 두 개를 먹었을 경우를 생각하면 된다.

세 가지의 식을 두었고, 해당 식들 중 max 값으로 dp 배열을 채워넣었다.

i ) ○●●: 현재와 직전 포도주를 먹고 그 전전 포도주는 무조건 먹지 않는 경우

dp1 = input[i] + input[i - 1] + dp[i - 3]

ii ) ?○●: 현재 포도주를 먹고 직전 포도주를 먹지 않는 경우 (전전 포도주의 먹는 여부는 신경쓰지 않음)

dp2 = input[i] + dp[i - 2]

iii ) ??○: 현재 포도주를 먹지 않는 경우 (전 포도주와 전전 포도주의 먹는 여부는 신경쓰지 않음)

dp3 = dp[i - 1]

 

dp1, dp2, dp3 중 가장 큰 값을 dp 값으로 지정하고, 알맞은 연속 여부에 대한 변수를 설정하여 구현하였다.

최종 코드는 다음과 같다.

 

#include <iostream>
using namespace std;

int input[10000];
int dp[10000];
int main(){

    int n;
    cin >> n;

    for(int i = 0; i < n; i++){
        cin >> input[i];
    }

    dp[0] = input[0];
    int check = 0;
    for(int i = 1; i < n; i++){
        dp[i] = dp[i-1] + input[i];
        check++;
        if(check >= 2){
            int temp1 = input[i - 1] + input[i];
            if(i >= 3)
                temp1 = input[i - 1] + input[i] + dp[i - 3]; // input[i] 선택 + input[i-1] 선택
            int temp2 = input[i] + dp[i - 2]; // input[i] 선택 + input[i-1] 선택 x
            int temp3 = dp[i - 1]; // input[i] 선택 x
            dp[i] = max(max(temp1, temp2), temp3);
            if(dp[i] == temp1)
                check = 2;
            else if(dp[i] == temp2)
                check = 1;
            else
                check = 0;
        }
    }

    cout << dp[n - 1] << endl;

    return 0;
}

 

https://github.com/haram1117/AlgorithmStudy/commit/8463a7a6cd01a1694bf0c38c30916120e808893c

DP2156 · haram1117/AlgorithmStudy@8463a7a