[BAE/<JOON> 문제풀이] 11052. 카드 구매하기 (DP.013)

https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

가방에 물건채우기 문제이다. 

 

사실 가방 물건 채우기를 배울 때 각각의 무게를 가지고 있는 문제보다 이러한 문제를 먼저 풀어보는게 가방 문제를 이해하는데 더 도움이 될 것 같다. (난 가방 문제 처음 볼 때 정답 코드를 보고도 이해하는데 오래걸렸다...)

 

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> arr, dp;
    arr.resize(n + 1);
    dp.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {//카드 종류
        for (int j = i; j <= n; j++) {//돈 합계
            if (dp[j] < dp[j - i] + arr[i]) {
                dp[j] = dp[j - i] + arr[i];
            }
        }
    }

    cout << dp[n];
    return 0;
}