[알고리즘 문제] 백준11052 - 카드 구매하기

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

11052번: 카드 구매하기

문제 자체는 그렇게 어려운게 아닌데 설명이 너무 깁니다...

 

민규는 N개의 카드를 사려고 합니다.

그리고 1~N개의 카드팩이 있는데 Pi에는 i개를 구매하는데 필요한 금액이 적혀 있습니다. 어쩃든 이 팩을 몇몇개를 구입해서 N개의 카드를 구매하는데 가장 큰 금액을 구하는 문제 입니다.

 

dp로 접근을 했고, 핵심은 dp[n]에는 n개의 카드를 사는데 필요한 최대 금액이 저장되어 있고 이 값을 사용하여 문제를 해결하였습니다.

 

그렇다면 고민해야 할 부분은 "어떻게 n개의 카드를 사는데 필요한 최대금액"을 구해야할까? 입니다.

 

예를 들어 5개의 카드를 구매한다고 가정해봅시다.

그렇다면 5개의 카드를 구매하는 방법에는 다음과 같이 있습니다.

 

카드5개

카드4개 + 카드1개

카드3개 + 카드2개

카드2개 + 카드3개

카드1개 + 카드4개

 

어쨋든 위의 방법중 하나는 카드5개를 구매하는데 최대금액일 것입니다. 여기서 각각의 N개의 카드를 구매하는데 최대금액은 dp[N]에 저장해놓았습니다. 

 

위의 경우를 에서 어떤 경우에 최대값을 가질지는 모릅니다. 하지만 위의 과정을 1번 반복하면 카드5개를 구매할 수 있는 최대값을 알 수 있겠네요. 

 

처음 1개를 구매할때의 최대금액은 비교할 상대가 없기 때문에 dp[1]에 card[1]을 넣어줍니다.2개부터는 1개를 2개 구매할지, 그냥 2개를 구매할지 선택해야 하기 떄문에 반복을 해줍니다.

 

결국 비교대상은 5개를 구매하는데 한번에 구매하는 경우(card[5])와 나눠서 구매하는 방법(dp[4] + dp[1], dp[3] + dp[2] ...)중 최대값을 구해야 합니다. 이미 dp[N]에는 dp[1] ~ dp[N-1]까지의 최대금익이 저장되어 있습니다.

 

안쪽 for문에서 dp[4] + dp[1], dp[3] + dp[2] ...)중 최대값을 구하고 마지막에 한번에 구매하는 경우(card[5])와 비교하여 큰 값을 dp[5]에 넣어줍니다.

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{

    int card[10002];
    int dp[1001];
    int N;

    cin >> N;

    for (int i = 1; i <= N; i++)
    {
        cin >> dp[i];
    }

    dp[1] = card[1];

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

    cout << dp[N];
    return 0;
}