항해99 코테

[C++] 99클럽 코테 스터디 12일차 TIL + 포도주 시식(백준 2156번)

탱도시락 2025. 4. 15. 20:11

✅ 오늘의 학습 키워드

  • 다이나믹 프로그래밍 or 동적 계획법 (Dynamic Programming = DP)

✅ 공부한 내용

✔️ 문제 요약

(백준 문제 링크: https://www.acmicpc.net/problem/2156)

포도주 시식회에서 일렬로 놓인 포도주를 마시려고 한다. 다음과 같이 두 가지 조건이 있다.

  1. 선택한 포도주는 모두 마셔야 한다.
  2. 연속으로 3잔을 모두 마실 수 없다.

각 포도주 잔에 들어있는 양이 주어질 때, 최대로 마실 수 있는 포도주의 양을 구하는 문제다.

✔️ 풀이 로직

이 문제는 동적 프로그래밍 접근법으로 해결해야한다.
각 위치에서 가능한 경우의 수를 고려하며 최대값을 누적해 나가는 방식이다.

  1. DP 배열을 정의: dp[i]는 i번째 잔까지 고려했을 때 마실 수 있는 최대 양
  2. 각 위치 i에서 가능한 경우:
    • i번째 잔을 마시지 않는다
    • i번째 잔을 마시고, i-1번째 잔은 마시지 않는다
    • i번째 잔과 i-1번째 잔을 마시고, i-2번째 잔은 마시지 않는다

3. 이를 점화식으로 표현: (❗참고❗ max 함수를 3개 이상 값에 대해 g++로 컴파일을 할 경우, -std=c++11로 해줘야한다. 일단 저는 그랬음... 흠흠..)

dp[i] = max(dp[i-1], dp[i-2] + amount[i], dp[i-3] + amount[i-1] + amount[i])

4. 초기 조건:

if (n >= 1) dp[1] = amount[1]; // 포도주가 1잔만 있을 경우, 그 1잔을 마신다
if (n >= 2) dp[2] = amount[1] + amount[2]; // 포도주가 2잔만 있을 경우, 두 잔 모두 마신다

✅ 오늘의 회고

- 😳 어떤 문제가 있었고, 나는 어떤 시도를 했는지

DP 문제를 잘 몰랐기에 점화식을 이번 기회에 처음 접해봤다. 처음에는 그냥 반복문으로 풀려고 시도했으나, 연속 3잔을 마실 수 없다는 제약 조건을 효율적으로 처리하기 어려웠다. (네! 그래서 답 봤습니다!)

그리고 max 함수 사용법에서도 오류가 있었다. 평소 터미널로 코딩을 하기에 g++로 직접 컴파일을 한다. 하지만 다음과 같은 에러가 뜬다.

이건 C++에서 3개 이상의 값을 비교할 때 initializer list를 사용하려면 C++11 이상의 컴파일러 옵션이 필요하다는 것이다.

- 🤔 어떻게 해결했는지

그래서 g++ -std=c++11 을 해주면 컴파일이 정상적으로 된다. 아니면 중첩된 max 함수를 사용하면 된다고 한다.

즉, 정리하면 !! C++에서 여러 값의 최댓값을 구하는 방법:

  • 중첩된 max 함수: max(a, max(b, c))
  • C++11 initializer list: max({a, b, c}) -> ex) g++ -std=c++11 bj_2156.cpp -o bj_2156

- 🤩 무엇을 새롭게 알았는지

  • DP의 핵심은 '최적 부분 구조'와 '중복되는 부분 문제'를 활용해 효율적으로 해를 구하는 것이다.
    • 최적 부분 구조(Optimal Substructure) - 이 문제는 더 작은 부분 문제의 최적해를 이용해 전체 문제의 최적해를 구할 수 있다. 즉, i번째 포도주까지 고려했을 때의 최대 양은 i-1, i-2, i-3번째 포도주까지 고려했을 때의 최대 양을 이용하여 계산한다.
    • 중복되는 부분 문제(Overlapping Subproblems) - 같은 계산을 여러 번 반복하게 된다. 예를 들어, 각 위치에서 연속 3잔을 마실 수 없다는 제약을 고려하면서 최대 양을 구하려면, 이전 위치들에서의 최대 양을 반복적으로 참조해야 한다.
  • 그리고 점화식을 세운다!!!! (이것도 어렵다!!!)

만약 그리디(Greedy) 알고리즘이나 완전 탐색(Brute Force)으로 풀려고 한다면:

  • 그리디는 지금이 최적인 선택이 전체적으로 최적이라는 보장이 없고 연속 3잔을 마실 수 없기에 이 문제에 적합하지 않다.
  • 완전 탐색은 가능한 모든 조합을 확인해야 하므로 n이 커지면 시간 복잡도가 O(2^n)으로 비효율적이다.

반면 DP는 O(n) 시간 복잡도로 해결할 수 있어 효율적이다. 이 문제는 최적 부분 구조와 중복되는 부분 문제라는 DP 적용의 두 가지 핵심 조건을 모두 만족하기 때문에 DP로 접근하는 것이 자연스럽다.

✅ 전체 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {

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

    vector<int> amount(n+1); // 인덱스 1부터 시
    for(int i = 1; i <= n; i++){
        cin >> amount[i]; 
    }

    vector<int> dp(n+1, 0); // DP 배열

    // 연속 2잔까지는 마실 수 있기 때문에 다음과 같은 조건 성립
    if (n >= 1) dp[1] = amount[1]; // 첫 번째 잔의 양이 최대
    if (n >= 2) dp[2] = amount[1] + amount[2]; // 첫 번째와 두번 째잔의 합이 최

    for(int i = 3; i <= n; i++){
        dp[i] = max({
                dp[i-1], // i번째 잔 마시지 않는 경우
                dp[i-2] + amount[i], // i번째 잔은 마시고, i-1번째 잔 X
                dp[i-3] + amount[i-1] + amount[i] // i, i-1번째 잔 마시는 경우
            });    
    }

    cout << dp[n] << endl; // 최대로 마실 수 있는 포도주의 양 출력

    return 0;

}