카드 구매하기 - 11052번 백준

문제 분류

문제 난이도 : 실버 1

문제 분류 : 다이나믹 프로그래밍

 

문제 리뷰

DP[j]를 j 개를 구매하는데에 걸리는 카드의 수로 정의한다.당연하게도, DP[0] = 0첫 번째 루프(i=1)에는 P_1만을 이용한다. DP[j] = P_1 * j가 된다.두 번째 루프(i=2)부터 비교를 해야한다. DP[j] = max(DP[j - 2] + P_2, DP[j])  초록색 부분은 i = 1일 때의 값이었을 것이다....따라서 DP[j] = max(DP[j - i]+ P_i, DP[j])가 된다.

 

문제 소스코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <unordered_set>
#include <memory.h>

using namespace std;

long Price[10001];
long long DP[1001];

void Init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    std::cout.tie(NULL);
}



int main()
{
    Init();
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> Price[i];
    }
    DP[0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= n; j++) {
            DP[j] = max(DP[j - i] + Price[i], DP[j]);
        }
    }
    cout << DP[n];

}