[백준] 2156번: 포도주 시식

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

문제

알고리즘 접근 방법

DP를 이용한다.

포도주의 양을 저장하는 배열 a, N번째 잔에서의 최댓값을 저장하는 배열 dp가 있다.
a[n]: n번째 포도주의 양
dp[n]: n번째 까지 마신 포도주의 최대 양

먼저 초기식을 구한다.

dp[0] = a[0] = 0
dp[1] = a[1]
dp[2] = a[1] + a[2]

3번째 부터는 반복문을 사용하여 구해준다.
3잔을 연속으로 마실 수 없기 때문에,
3번째 잔에서의 최댓값(dp[3])은

1. a[1] + a[3] ㅁ _ ㅁ
2. a[2] + a[3] _ ㅁ ㅁ
3. a[1] + a[2] ㅁ ㅁ _

이런 식이다.

그럼 N번째 잔에서의 최댓값은

1. N-3번째까지의 최댓값 + N-1번째 잔 + N번째 잔 _] _ㅁ ㅁ
2. N-2번째까지의 최댓값 + N번째 잔 _ _] _ ㅁ
3. N-1번째까지의 최댓값(N선택 X) _ _] _

N번째라고 해서 꼭 N번째 잔을 선택할 필요가 없음에 유의하자.

이를 토대로 점화식을 세우면
dp[n] = max({dp[i-3]+a[i-1]+a[i], dp[i-2]+a[i], dp[i-1]})

풀이

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    
    int n;

    cin >> n; // 포도주 잔의 개수

    int a[n+1] = {0,};
    for (int i=1; i<=n; i++)
        cin >> a[i]; // 각 포도주의 양


    long long dp[n+1]; // n개의 잔을 마셨을 경우 최대의 값
    
    

    // 1번째 잔과 2번째 잔의 경우는 직접 세팅해준다. 

    dp[0] = 0; 
    dp[1] = a[1];
    dp[2] = a[1] + a[2];

    for (int i=3; i<=n; i++){

        // N번째 와인잔을 선택했을 때 마실 수 있는 경우의 수
        // 1. N-3번째까지의 최댓값 + N-1번째 잔 + N번째 잔 _] _ㅁ ㅁ
        // 2. N-2번째까지의 최댓값 + N번째 잔 _ _] _ ㅁ
        // 3. N-1번째까지의 최댓값(N선택 X) _ _] _ 

        dp[i] = max({dp[i-3]+a[i-1]+a[i], dp[i-2]+a[i], dp[i-1]});
    }

    cout << dp[n] << endl;
    

    return 0;
}

정리

처음 내가 생각한 알고리즘은 예제는 맞았으나 여러 반례에서 틀렸음을 알 수 있었다.
사실 그 풀이는 아직 어느 부분에서 오류인지 모르겠음 ..
아마 2개를 건너뛸 수도 있는 경우를 생각하지 못했던 걸로 추측한다. 어려운 문제였다 ㅠㅠ

💡 참고 포스팅

kimyuunseok님 블로그
yabmoons님 블로그