[BOJ] 11052: 카드 구매하기(C++)

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

11052번: 카드 구매하기

문제 요약

민규가 N장의 카드를 사려고 하고 1,2,3,...N 장의 카드팩 가격이 주어진다. 민규는 가장 많은 돈을 지불하여 N장의 카드를 살 것이다. 카드팩의 조합으로 민규가 지불하게 될 돈을 구해라

풀이

민규가 각 카드를 사용하는 방법은 다음과 같다.

1. 그 카드로만 지불한다.

2. 카드와 다른 카드를 합쳐서 지불한다.

 

2장의 카드를 구매한다고 가정해보자.

2장의 카드는 2장 카드팩을 구매하는 경우와 1장 카드팩을 2개 구매하는 경우 중 최대 가격으로 구매할 것이다.

 

그렇다면 3장의 카드를 구매한다고 가정해보자.

3장의 카드는 3장의 카드팩으로 구매하는 경우와, 2장의 카드팩과 1장의 카드팩을 합쳐 구매하는 경우, 그리고 1장의 카드팩을 3개로 구매하는 경우 중 최대 가격으로 구매할 것이다. 

 

여기서 dp 배열에 각 카드를 구매하는 최대의 가격을 저장을 해놓으면 dp[2]에는 이미 최대 금액이 저장되어 있기 때문에 3장 카드팩의 가격과 dp[2]+ 1장 카드팩의 가격만 비교하면 된다.

 

다시 4장의 카드를 구매한다고 생각해보자. 

4장의 카드는 2장 카드팩 2개와 4장 카드팩 1개, 그리고 3장 카드팩 1개, 1장 카드팩 1개의 경우와 마지막으로 1장 카드팩 4개의 경우를 따져줘야한다. 여기서 3장 카드팩 1개, 1장 카드팩 1개의 경우는 이미 따진 경우이므로 2장 카드팩 2개를 생각해야한다. 

 

여기서 생각의 전환이 필요했다. 작은 수가 아니라 큰 수가 들어왔을 때도 경우를 다 따지려면 중첩 반복문이 필요했다.

 

그렇게 나온 점화식은 다음과 같다.

for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            dp[i] = max(dp[i], dp[i - j] + input[j]);
        }
    }

 

정답 

#include <iostream>

using namespace std;

int dp[1001];

int main() {
    int N;
    cin >> N;
    int *input = new int(N+1);

    for (int i = 1; i <= N; i++) {
        cin >> input[i];
    }
    dp[0] = input[0] = 0; // 초기화

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            dp[i] = max(dp[i], dp[i - j] + input[j]);
        }
    }
    cout << dp[N];
    return 0;
}