[algorithm] 백준 - 카드 구매하기

이 문제는 전형적인 DP 문제이다.

포인트는 N개의 카드팩을 사는데 가장 비싼 값을 반환하는 것이다.

 

이 곳에는 DP 배열과 P 배열을 변수로 사용한다.

DP 배열은 n개의 카드팩을 사는 방법 중 가장 큰 돈으로 살 수 있는 경우를 저장한다.

P 배열은 카드 n개가 포함된 카드팩의 값을 저장한다.

예를 들어보자,

카드팩을 4개 산다고 가정했을 때

DP[4] = max(

P[4] + DP[4 - 4 = 0],

P[3] + DP[4 - 3 = 1],

P[2] + DP[4 - 2 = 2],

P[1] + DP[4 - 1 = 3]

)

가 되고,

이를 구하기 위해선 DP[0], DP[1], DP[2], DP[3]을 필요로 하게 된다.

 

그럼 이를 식으로 표현해보면,

DP[N] = max(P[N] + DP[N - i], DP[N])이 되고,

반복문을 통해 DP[0], DP[1], DP[2], DP[3]를 구한다.

그러면

for(int j = 1; j <= i; j++){
    dp[i] = max(dp[i], dp[i - j] + p[j]);
}

이렇게 표현할 수 있다.

 

코드는

// 카드 구매하기
#include <iostream>
using namespace std;

int main(void){
    int count, num;
    cin >> count;
    int p[10001], dp[10001] = {0};
    for(int i = 1; i <= count; i++){
        cin >> num;
        p[i] = num;
    }
    for(int i = 1; i <= count; i++){
        for(int j = 1; j <= i; j++){
            dp[i] = max(dp[i], dp[i - j] + p[j]);
        }
    }
    cout << dp[count];
}

https://github.com/jeongdaeun98/algorithm/blob/master/2020/20110201.cpp