[BOJ] 11052 : 카드 구매하기

풀이

시간복잡도 O(n^2)

p[i] 카드i장이들은 팩 가격

d[i] 카드i장을 구매하는 최대 비용

d[i] = max( d[i-1] + p[1] , d[i-2]+p[2] … )

코드

#include <iostream>
using namespace std;

int p[1001];
int d[1001];

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

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
        d[i] = p[i];
        for (int j = 1; j < i; j++) {
            if (d[i] < p[j] + d[i - j])
                d[i] = p[j] + d[i - j];
        }
    }
    cout << d[n];
    return 0;
}

Written on March 14, 2019