Beakjoon 11052 카드 구매하기

19 Feb 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/11052

나의 풀이

DP[i] = i개 카드를 살 수 있는 금액의 최댓값
1개 카드를 살 수 있는 최대값 DP[1] = P_1
DP[2]는 1개 카드를 두번 사는 경우와 2개 들어있는 카드팩 1개를 사는 경우가 있다.
DP[2] = max(DP[1] + DP[2-1], P_2) = max(DP[1] + DP[1], P_2)
DP[3]은 2개 카드를 사는 경우에서 1개 카들를 추가로 사는 경우와 3개의 카드가 들어있는 카드팩 1개를 사는 경우가 있다. DP[3] = max(DP[1] + DP[3-1], P_3) = max(DP[1] + DP[2] , P_3)
DP[4]는 카드 3개와 카드 1개를 사는 경우와 카드 2개를 2번 사는 경우, 4개의 카드가 들어있는 카드팩 1개를 사는 경우가 있다.
DP[4] = max(DP[1] + DP[4-1], DP[2] + DP[4-2], P_4) = max(DP[1] + DP[3], DP[2] + DP[2], P_4)
마찬자지로 DP[5]도 정리하면 다음과 같다.
DP[5] = max(DP[1] + DP[5-1], DP[2] + DP[5-2], P_5) = max(DP[1] + DP[4], DP[3] + DP[2], P_5)
위와 같은 규칙으로 DP[i]를 일반화 하면 다음과 같다.
DP[i] = max(DP[1]+DP[i-1], DP[2] + DP[i-2], DP[3] + DP[i-3] …, DP[i/2] + DP[i-i/2], P_i)
결과적으로 N개의 카드를 구매하기 위해 지불해야 하는 금액의 최댓값은 DP[N]이다.

풀이 코드 : 11052 카드 구매하기

#include <iostream>
#include <vector>

using namespace std;

int DP[1001];

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

    int N;
    cin>>N;
    
    vector<int> P;
    P.resize(N+1);
    for(int i=1;i<=N;i++){
        cin>>P[i];
        DP[i] = P[i];
    }

    for(int i=1;i<=N;i++){
        for(int j=1;j<=i/2;j++){
            if(DP[i] < DP[j] + DP[i-j])
                DP[i] = DP[j] + DP[i-j];
        }
    }

    
    cout<<DP[N];
}

채점결과