백준 11052 : 카드 구매하기

문제 링크입니다 https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

카드 N개를 구매하기 위해 지불해야 하는 금액의 최댓값을 구하는 문제였습니다. 점화식을 구하기 위해 "D[N] : N개의 카드를 구매하기 위해 지불해야 하는 금액의 최댓값"이라 해보면, P[i]는 i개의 카드가 포함된 카드팩의 가격이므로,

 

[1] D[N] = D[N-1] + P[1]

→ N-1개의 카드를 구매하기 위해 지불해야 하는 금액의 최댓값 + 1개 구매

[2] D[N] = D[N-2] + P[2]

→ N-2개의 카드를 구매하기 위해 지불해야 하는 금액의 최댓값 + 2개 구매

[3] D[N] = D[N-3] + P[3]

→ N-3개의 카드를 구매하기 위해 지불해야 하는 금액의 최댓값 + 3개 구매

...

[N] D[N] = D[N-N] + P[N]

→ N-N개의 카드를 구매하기 위해 지불해야 하는 금액의 최댓값 + N개 구매

 

결국, D[N]을 구하는 것은, 즉, N개의 카드를 구매하기 위한 금액의 최댓값을 구하는 것은 [1], [2], [3], ... [N] 중에서 최댓값을 찾는 것과 동일하게 됩니다. 문제 해결 코드는 다음과 같습니다.

 

 

[소스코드]

 

#include<algorithm>
#include<cstdio>
using namespace std;
const int MAX = 1000 + 10;
 
// DP[n] : n개의 카드를 구매하기 위해 지불해야 하는 금액의 최댓값
int n, p[MAX], DP[MAX];
 
int main(void) {
    scanf("%d", &n);
 
    // 1개짜리부터 n개짜리 카드팩의 가격을 입력받습니다
    for (int i = 1; i <= n; i++) {
        scanf("%d", &p[i]);
    }
    
    // 1개짜리부터 n개짜리까지 최댓값을 DP 배열에 저장합니다
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
 
            DP[i] = max(DP[i], DP[i - j] + p[j]);
            // DP[1] = max(DP[1], DP[0] + p[1])
            // DP[2] = max(DP[2], DP[1] + p[1]), max(DP[2], DP[0] + p[2])
            // ...
            // 모든 DP[i]에 대해 [1] ~ [N] 중 최댓값을 찾는 코드가 됩니다
        }
    }
 
    printf("%d", DP[n]);
    return 0;
}