[#11052] 카드 구매하기

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
 
int main() {
    int n;
    cin >> n;
 
    vector<int> price(n + 1);  
    vector<int> dp(n + 1, 0);  //dp[i]: n이 i일때 지불해야 하는 최대값
 
    for (int i = 1; i <= n; i++) {
        cin >> price[i];
    }
 
    /*
    dp[n] = max(dp[1]+dp[n-1], dp[2]+dp[n-2], ... , dp[n-1]+dp[1], Pn)
    여기서 n/2를 기준으로 같은 값이 2번씩 비교되므로
    dp[n] = max(dp[1]+dp[n-1], dp[2]+dp[n-2], ... , dp[n/2]+dp[n-n/2], Pn)
    */
 
    dp[1] = price[1];
 
    int maxVal;
    for (int i = 2; i <= n; i++) {
        maxVal = -1;
        for (int j = 1; j <= i / 2; j++) {
            if (maxVal < dp[j] + dp[i - j])
                maxVal = dp[j] + dp[i - j];
        }
        maxVal = max(maxVal, price[i]);
        dp[i] = maxVal;
    }
 
    cout << maxVal;
 
    return 0;
}

 

처음에는 1장당 가격이 비싼 카드팩부터 사는 그리디를 생각했었는데

n=3일때 P1 = 1, P2 = 100, P3 = 160, P4 =1

이라고 하면 1장당 가격은 P3, P2, P1, P4 순이므로 P3를 하나(1개만 더 사야됨), P1을 하나 총 161를 낸다.

하지만 P2를 두개 사면 200을 내야하고 최적해를 찾지 못한다.

 

dp 점화식을 생가해보면

n=1, dp[1] = P1

n=2, dp[2] = max(dp[1]+dp[1], P2)

n=3, dp[3] = max(dp[1]+dp[2], dp[2]+dp[1], P3)

n=4, dp[4] = max(dp[1]+dp[3], dp[2]+dp[2], dp[3]+dp[1], P4)

...

n=n, dp[n] = max(dp[1]+dp[n-1], dp[2]+dp[n-2], ... ,  dp[n-2]+dp[2], dp[n-1]+dp[1], Pn)

 

이 때, 같은 색끼리 중복됨 (n/2를 기준으로 같은 값이 2번씩 비교됨) 
따라서 dp[n] = max(dp[1]+dp[n-1], dp[2]+dp[n-2], ... , dp[n/2]+dp[n-n/2], Pn)