[ 백준 16194 ] 카드 구매하기2 (C++)

백준의 카드 구매하기2(16194) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

카드 N장을 갖기 위해서 지불해야 하는 금액의 "최솟값"을 구해야 하는 문제이다.

이 문제를 풀기 전에 다음 문제를 먼저 풀어본 후, 풀이까지 보고 오는 것을 권장한다.

[ 백준 - 카드 구매하기(11052) 문제 바로가기 ]

[ 백준 - 카드 구매하기(11052) 풀이 바로가기 ]

위의 문제와 이 문제의 가장 큰 차이점은, N장의 카드를 갖기 위해서 지불해야하는 금액의 "최댓값"을 구하냐, "최솟값"을 구하냐의 차이이다. (전체적인 로직이 동일합니다. 따라서 구체적인 설명은 위의 11052번 풀이로 대체하겠습니다.)

따라서 위의 풀이글과 동일한 로직으로 풀되, 금액을 최솟값을 구하도록 연산을 바꿔주어야 한다.

최댓값을 구하는 방법에 대해서 간략하게만 이야기하자면 다음과 같이 구하였다.

A장의 카드를 갖기 위해서, A - K 장의 카드를 가질 때 드는 최대금액에 K장짜리 카드팩을 구매하는 것

으로 구하였었다.

즉, A장의 카드를 갖기 위해서 지불해야 하는 금액의 최댓값은

기존의 A장의 카드를 갖기 위해 지불했었던 금액의 최대금액 vs A - K장의 카드를 가질 때 지불해야 하는 최대금액 + K장짜리 카드팩을 구매할 때 드는 비용

중 더 큰 비용을 A장의 카드를 갖기 위해서 지불해야 하는 금액으로 설정해 주었다.

이 문제에서는 반대로 설정을 해주면 된다.

기존의 A장의 카드를 갖기 위해 지불했었던 금액의 최소금액 vs A - K장의 카드를 가질 때 지불해야 하는 최소금액 + K장짜리 카드팩을 구매할 때 드는 비용

이라는 점화식을 통해서 이 문제를 해결할 수 있다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 1010
using namespace std;
 
int N;
int Card[MAX];
int DP[MAX];
 
int Min(int A, int B) { return A < B ? A : B; }
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> Card[i];
}
 
void Solution()
{
    DP[1] = Card[1];
    for (int i = 2; i <= N; i++)
    {
        DP[i] = Card[i];
        for (int j = 1; j <= i; j++)
        {
            DP[i] = Min(DP[i], DP[i - j] + Card[j]);
        }
    }
    cout << DP[N] << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}