[C++][DP] 백준 11052번 : 카드 구매하기

🏆 목차.

1. 문제
2. 코드
3. 풀이

 

🛒 문제

 

11052번: 카드 구매하기

 

🎨 코드

 

#include<iostream>
#include<vector>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> dp(n + 1, 0);
    vector<int> arr(1001,0);
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i];
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            dp[i] = max(dp[i], dp[i - j] + arr[j]);
        }
    }
    cout << dp[n];
}

 

🎯 풀이

 

11052번 카드 구매하기는 다이내믹 프로그래밍을 이용해 푸는 문제입니다.

문제를 해결하기까지 이해가 되지 않아 많은 어려움이 있었습니다.

 

문제를 정리하자면

카드 N개를 구매해야하고,

카드팩의 종류는 N가지 종류가 존재하고,

i번째 카드팩은 i개의 카드를 담고 있으며,가격은 P [i] 원입니다.

 

쉬운 이해를 위해 그림을 이용하여 풀이하겠습니다.

 

문제 풀이 그림

 

마지막 카드팩은 i개의 카드를 가지고 있고 해당 카드를 제외한 카드팩은 N-i의 카드를 가지고 있습니다.

위 규칙을 통해 dp [N] = dp [N-i] + p [i]를 구할 수 있었습니다.

 

현재 자기 자신이 가지고 있는 값과 결괏값을 비교하면 최대비용을 구할 수 있습니다.

            dp [i] = max(dp[i], dp[i - j] + arr [j]);