[백준 11052] 카드 구매하기 (DP, 점화식)

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

11052번: 카드 구매하기

문제 설명이 조금 길고 복잡해 보이지만, 전형적인 DP문제이다!
문제풀이를 위해 필요한 부분만 정리하자면 아래와 같다.

"최대한 많이 지불해서 카드 N개 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다."

예를 들어, 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값은 10원이다. 2개 들어있는 카드팩을 2번 사면 된다.

 

문제를 이해했다면, 이제 점화식을 만들기 위한 규칙을 찾아보자.

 

• 구매하고싶은 카드의 장수를 N개,  arr[i]에는 입력받은 카드팩별 가격을 저장한다. 이때,i장이 들어있는 카드팩의 가격은 arr[i]에 저장한다.
• dp[i]에는 i장의 카드를 구매하기 위한 최대 금액을 저장한다.

 

편의상, arr[1]~arr[4]를 ①②③④로 나타내었습니다.

---

<소스코드>

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
int compare(int n1, int n2) {
    return n1 > n2 ? n1 : n2;
}
 
int main() {
    int N, max;
    int result = 0;
    int dp[10001] = { 0, };
    int arr[10001] = { 0, };
 
    //입력받기
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
 
    //
    if (N == 1) {
        printf("%d", arr[1]);
        return 0;
    }
    dp[1] = arr[1];
    result = dp[1];
    for (int i = 2; i <= N; i++) {
        max = arr[i];
        for (int j = 1; j <= i - 1; j++) {
            max = compare(max, dp[j] + arr[i - j]);
        }
        dp[i] = max;
        result = compare(max, result);
    }
 
    printf("%d", result);
    return 0;
}