Silver I 난이도의 동적 프로그래밍 문제를 C++로 풀이한 내용입니다. n개의 포도주 잔이 일렬로 놓여있을 때, 연속 3잔을 마시지 않는 제약 조건 하에서 최대한 많은 포도주를 마시는 문제입니다.

백준 2156: 포도주 시식

문제 소개

이 문제는 다음과 같은 조건을 만족하며 최대 포도주 양을 구하는 것입니다:

n개의 포도주 잔이 순서대로 놓여있음
각 잔은 마시거나 마시지 않을 수 있음
제약: 연속된 3잔을 모두 마실 수 없음
목표: 최대 포도주 양 구하기

예를 들어 n=3, 각 잔의 양이 6, 10, 5라면, 첫 번째와 두 번째만 마셔서 16을 얻습니다.

접근 방법

이 문제는 시간축 동적 프로그래밍으로 해결합니다. 핵심은 "연속 3잔 금지"라는 제약을 다르게 해석하는 것입니다.

논리적 변환: 각 위치 i에 대해, i번째 포도주를 포함한 최적 해를 구할 때, 마지막 3칸(i, i-1, i-2) 중 반드시 하나는 "마시지 않은 지점"이 존재해야 합니다.

이를 통해 모든 합법적인 경우를 정확히 3가지로 완전히 분해할 수 있습니다:

Case 1: i번째를 마시지 않음 → dp[i-1]
Case 2: i-1번째를 마시지 않음 → dp[i-2] + wine[i]
Case 3: i-2번째를 마시지 않음 → dp[i-3] + wine[i-1] + wine[i]

이 3가지 외에는 존재 불가능합니다(세 잔을 모두 마시면 연속 3잔 위반).

풀이 과정

1단계: 입력 및 초기화

n개의 포도주 양을 입력받고, dp 배열을 초기화합니다.

2단계: 기저 사례 설정

dp[1] = wine[1] (첫 잔만 마심)
dp[2] = wine[1] + wine[2] (첫 두 잔을 모두 마심)

3단계: 점화식 적용

i = 3부터 n까지 위의 3가지 경우의 최댓값을 선택합니다.

4단계: 답 출력

dp[n]이 최종 답입니다.

코드 설명

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    // wine[i] = i번째 포도주의 양 (1-indexed)
    vector<int> wine(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> wine[i];
    }

    // dp[i] = 1 ~ i번째 포도주까지 고려했을 때 얻을 수 있는 최대 양
    vector<int> dp(n+1, 0);

    // 기저값
    if (n >= 1) dp[1] = wine[1];
    if (n >= 2) dp[2] = wine[1] + wine[2];

    /*
        핵심 아이디어 (시간축 DP):

        "연속 3잔 금지"라는 제약은 논리적으로:
        -> 마지막 3칸(i, i-1, i-2) 중
           반드시 하나는 '안 마신 지점'이 있어야 한다.

        즉, 합법적인 모든 경우는
        "마지막으로 안 마신 시점"이 어디냐로
        딱 3가지로 완전 분해된다.

        Case 1: i번째를 안 마신다
            패턴: ... - _
            dp[i-1]

        Case 2: i-1번째를 안 마신다
            패턴: ... - _ -
            dp[i-2] + wine[i]

        Case 3: i-2번째를 안 마신다
            패턴: ... - _ - -
            dp[i-3] + wine[i-1] + wine[i]

        이 3개 말고는 존재 불가능.
        (i, i-1, i-2 전부 마시면 3연속 위반)
    */

    for (int i = 3; i <= n; i++) {
        dp[i] = max({
            dp[i-1],                              // Case 1: 이번에 안 마심
            dp[i-2] + wine[i],                    // Case 2: i-1에서 끊김
            dp[i-3] + wine[i-1] + wine[i]         // Case 3: i-2에서 끊김
        });
    }

    cout << dp[n];
}

주요 부분 설명:

벡터 초기화: 1-indexed 벡터를 사용하여 포도주 번호와 배열 인덱스를 일치시킵니다.
기저값 설정: n=1, 2인 경우를 미리 처리하여 인덱스 오류를 방지합니다.
점화식: max() 함수로 3가지 경우를 비교하여 최댓값을 선택합니다.
빠른 입출력: ios::sync_with_stdio(false) 사용으로 성능을 최적화합니다.

복잡도 분석

시간 복잡도: O(n)

단일 반복문이 n번 실행되고, 각 반복에서 상수 시간 연산만 수행합니다.

공간 복잡도: O(n)

dp 배열과 wine 배열 각각 O(n) 공간을 사용합니다.
공간 최적화: 실제로는 직전 3개의 값만 필요하므로 O(1)로 줄일 수 있습니다.

배운 점

제약 조건의 논리적 변환: "연속 3잔 금지"를 "마지막 3칸 중 하나는 안 마신다"로 재해석하면 점화식 도출이 명확해집니다.
상태 정의의 중요성: dp[i]를 "i번째까지 고려했을 때의 최댓값"으로 정의하면, 각 단계에서 독립적으로 최적 선택을 할 수 있습니다.
완전 분해: 복잡한 제약 조건도 논리적으로 완전히 분해하면 작은 경우들의 합으로 표현 가능합니다. 이는 DP 문제 해결의 핵심 전략입니다.
다른 문제에의 응용: "최대 k개 연속 사용 금지" 패턴의 문제들에 이 접근법을 적용할 수 있습니다.