C++ 동적 계획법으로 풀어보는 와인 판매 최대 수익 문제

문제 정의

n개의 와인이 일렬로 놓여 있으며, 각 와인의 가격을 나타내는 정수 배열이 주어집니다. 매년 한 번씩 맨 앞(start) 또는 맨 뒤(end)에 있는 와인을 하나씩 판매할 수 있습니다.

와인의 가격은 시간이 지남에 따라 상승하는데, 초기 수익을 P1, P2, P3 … Pn이라고 하면 Y번째 해에 i번째 와인을 판매할 때 얻는 수익은 Y × Pi가 됩니다. 즉, 나중에 팔수록 더 많은 수익을 얻게 됩니다.

당신의 과제는 다음 두 가지입니다.

• 매년 어떤 와인을 판매해야 하는지 'start' 또는 'end'로 출력하기
• 모든 와인을 판매했을 때 얻을 수 있는 최대 총 수익 계산하기

예시

와인 가격이 {2, 4, 6, 2, 5}일 때 출력 결과:
start end end start start
최대 수익 = 64

접근 방식: 동적 계획법

이 문제는 그리디 방식으로는 항상 최적해를 보장할 수 없기 때문에, 동적 계획법(Dynamic Programming)을 사용해야 합니다.

• 핵심 아이디어는 각 구간 [begin, end]에 대해 얻을 수 있는 최대 수익을 메모이제이션(memoization)으로 저장하는 것입니다.
• 동시에 해당 상태에서 어느 쪽(앞 또는 뒤)의 와인을 판매했는지 기록해 두면, 처음 상태부터 이 기록을 따라가면서 최적의 판매 순서를 복원할 수 있습니다.

Y번째 해에는 남아 있는 와인이 n − (end − begin)개만큼 팔렸으므로, 현재 연도는 n - (end - begin)으로 계산됩니다. 전체 시간 복잡도는 O(n²)입니다.

구현 예제 (C++)

#include <bits/stdc++.h>
using namespace std;
#define N 1000
int dp[N][N];
int sell[N][N];
int maxProfitUtil(int price[], int begin, int end, int n) {
    if (dp[begin][end] != -1) {
        return dp[begin][end];
    }
    int year = n - (end - begin);
    if (begin == end) {
        return year * price[begin];
    }
    int x = price[begin] * year + maxProfitUtil(price, begin + 1, end, n);
    int y = price[end] * year + maxProfitUtil(price, begin, end - 1, n);
    int ans = max(x, y);
    dp[begin][end] = ans;
    if (x >= y) {
        sell[begin][end] = 0;
    } else {
        sell[begin][end] = 1;
    }
    return ans;
}
int maxProfit(int price[], int n) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            dp[i][j] = -1;
        }
    }
    int ans = maxProfitUtil(price, 0, n - 1, n);
    int i = 0, j = n - 1;
    while (i <= j) {
        if (sell[i][j] == 0) {
            cout << "start ";
            i++;
        } else {
            cout << "end ";
            j--;
        }
    }
    cout << endl;
    return ans;
}
int main() {
    int price[] = { 2, 4, 6, 2, 5 };
    int n = sizeof(price) / sizeof(price[0]);
    int ans = maxProfit(price, n);
    cout << "Maximum profit = " << ans << endl;
    return 0;
}

코드 설명

• dp[begin][end]: 남은 와인 구간이 [begin, end]일 때 얻을 수 있는 최대 수익을 저장합니다. -1로 초기화하여 아직 계산되지 않은 상태임을 표시합니다.
• sell[begin][end]: 해당 구간에서 최적 선택이 무엇이었는지 저장합니다. 0이면 맨 앞(start), 1이면 맨 뒤(end)의 와인을 판매한 경우입니다.
• maxProfit() 함수는 메모이제이션 테이블을 초기화한 뒤 최대 수익을 계산하고, sell 테이블을 처음부터 끝까지 추적하며 최적 판매 순서를 출력합니다.

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.

start end end start start
Maximum profit = 64

즉, 첫 해에는 가격 2짜리 맨 앞 와인을, 이후에는 뒤쪽 와인들을 우선적으로 판매하는 전략이 총 수익 64라는 최댓값을 만들어냅니다.