BOJ 11052 · 카드 구매하기

알고리즘 분류 : 다이나믹 프로그래밍  

DP를 통해 카드를 구매하기 위해 지불하는 금액의 최댓값을 구해야 한다.

• D[N] : 카드 N장을 구입하기 위한, 지불 금액의 최댓값
• D[0] = 0, D[1] = P[1]
• D[N-1] + P[1] : 카드 1개 들어있는 카드팩을 구매하고, 카드 N-1장을 구매한 지불 금액의 최댓값
• D[N-2] + P[2]
• ‥‥
• D[0] + P[N] : 카드 N개 들어있는 카드팩을 구매하고, 카드 0장을 구매한 지불 금액의 최댓값

---

C++ 소스코드

#include <cstdio>
#include <algorithm>
using namespace std;

int n, d[1001], p[1001];

void solve() {
    d[0] = 0, d[1] = p[1];
    for (int i=2; i<=n; i++) {
        for (int j=1; j<=i; j++) {
            d[i] = max(d[i], d[i-j]+p[j]);
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i=1; i<=n; i++) scanf("%d", &p[i]);
    solve();
    printf("%d\n", d[n]);
    return 0;
}

---

Python 3 소스코드

n = int(input())
d = [0]*(n+1)
p = [0]+list(map(int, input().split()))

def solve():
    d[0], d[1] = 0, p[1]
    for i in range(2, n+1):
        for j in range(1, i+1):
            d[i] = max(d[i], d[i-j]+p[j])

solve()
print(d[n])

---

참고

• 백준 온라인 저지 : BOJ 11052