백준 11052 - 카드 구매하기

문제

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

11052번: 카드 구매하기

 

풀이

1부터 N까지의 수 중에서 조합을 해서 N을 만드는 경우의 최대값을 구하는 문제이다. 

 

D[N]을 N개를 갖기 위해 지불하는 최대 금액으로 한다.

N이 4라고 하고 P[1] ~ P[4]까지 카드의 금액이 주어진다고 하면

○ + ○ + ○ + ● = 4 에서

●에 올 수 있는 수는 1, 2, 3, 4 가 된다.

그럼 가능한 점화식은 다음이 된다.

D[4] = max {

    D[4-1] +P[1],

    D[4-2] + P[2],

    D[4-3] + P[3],

    D[4-4] + P[4] = D[0] + P[4]

}

 

이 점화식을 일반화 하여 문제를 해결한다.

D[N] = max {

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

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

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

    ......

    D[N-N] + P[N]

}

코드

탑다운 방식

 

#include <iostream>
#include <algorithm>
using namespace std;
int N;
int P[1001];
int dp[1001];
int f(int N)
{
    if (N == 0) return 0;
    if (dp[N]) return dp[N];
    int result = 0;
    for (int i = 1; i <= N; i++)
        result = max(result, f(N - i) + P[i]);
    return dp[N] = result;
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> P[i];
    cout << f(N);
    return 0;
}
 

 

바텀업 방식

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int N;
int P[1001];
int dp[1001];
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> P[i];
 
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            dp[i] = max(dp[i], dp[i - j] + P[j]);
        }
    }
 
    cout << dp[N];
 
    return 0;
}