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

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

[ 문제 바로가기 ]

[ 문제풀이 ]

N장의 카드를 구매할 때, 지불해야 하는 최대금액을 구해야 하는 문제이다.

간단한 예시를 통해서 문제에 접근해보자.

N = 5 이고, 카드 팩의 가격이 { 1 , 4 , 2 , 7 , 3 } 이라고 가정해보자.

그리고 지금부터 카드 1장을 사는 것 부터, 카드 5장을 사는 과정까지 쭉 알아보자.

또한, 지금부터 연산한 결과 값들에 대한 내용을 보다 쉽게 표현하기 위해서 F[A] = B 라는 수식을 사용할 것이다.

F[A] = B의 의미는 "A장의 카드를 사는데 지불해야 하는 최대 금액은 B원입니다." 를 의미한다.

가장 먼저 1장의 카드를 구매하는 방법을 알아보자.

카드 1장을 구매하기 위해서는 구매할 수 있는 방법이 딱 한 가지 밖에 존재하지 않는다.

바로 1개의 카드가 포함된 카드팩 하나를 사는 것 밖에 없다.

이 외의 방법은 1장을 초과해 버리기 때문에 카드가 1장이 들어있는 카드팩을 사는 경우 밖에 존재하지 않는다.

따라서 1장을 살 때, 지불해야 하는 최대금액은 1원이 된다.

F[1] = 1

2장의 카드를 구매하는 방법을 알아보자.

이 경우에는 2가지 방법이 있다.

1. 1장의 카드가 들어있는 카드팩을 2개 사는 경우

2. 2장의 카드가 들어있는 카드팩을 1개 사는 경우

1번 Case같은 경우에는 1 + 1 = 2원이 되고 , 2번 Case같은 경우에는 4원이 되기 때문에 2장의 카드를 구매할 때 지불해야 하는 최대금액은 위의 2가지 Case중 더 큰 값인 '4원'이 된다.

F[2] = 4

3장의 카드를 구매하는 방법을 알아보자.

먼저, 3장의 카드를 구매할 수 있는 모든 방법을 알아보자.

1. 1장의 카드가 들어있는 카드팩을 3개 사는 경우

2. 2장의 카드가 들어있는 카드팩 1개를 사고 1장의 카드가 들어있는 카드팩 1개를 사는 경우

3. 3장의 카드가 들어있는 카드팩 1개를 사는 경우

위와 같이 3가지 경우가 존재할 수 있다. 결과부터 확인해보자.

Case1 : 1장의 카드가 들어있는 카드팩을 3개 사는 경우 = 3원

Case2 : 2장의 카드가 들어있는 카드팩을 1개 사는 경우 = 4원 + 1장의 카드가 들어있는 카드팩을 1개 사는 경우 1원 = 5원

Case3 : 3장의 카드가 들어있는 카드팩 1개를 사는 경우 = 2원

즉 ! 위의 경우에서는 가장 큰 값인 Case2가 3장의 카드를 구매할 때 지불해야 하는 최대금액이 된다.

F[3] = 5

그런데 ! 여기서 그냥 넘어가지 말고 몇 가지만 체크해 보고 넘어가자.

간단하게 표현하기 위해서 카드팩을 가격을 Card[A] = B라고 표현하겠다.

예를 들어서 Card[1] = B 는 "1장의 카드가 들어있는 카드팩의 가격은 B원입니다." 를 의미한다.

즉 ! 우리가 계산하고 예시를 위의 표현방법으로 나타내보면

Card[1] = 1 , Card[2] = 4 , Card[3] = 2 , Card[4] =  7 , Card[5] = 3 이 되는 것이다.

Case1을 식으로 나타내보면 Card[1] + Card[1] + Card[1] 이 된다.

Case2를 식으로 나타내보면 Card[2] + Card[1] 이 된다.

Case3을 식으로 나타내보면 Card[3] 이 된다.

조금만 더 다르게 표현해보면 이렇게 표현할 수 있다.

Case1 : Card[1] + 2장의 카드를 구매하는 경우

Case2 : Card[2] + 1장의 카드를 구매하는 경우

Case3 : Card[3] + 0장의 카드를 구매하는 경우

그런데 문제는 위에서 초록색으로 표시된 Case1 ~ 3 과 파랑색으로 표시된 Case1 ~ 3이 서로 같은 결과값을 갖는지 혹은 서로 같은 의미를 가지고 있는 수식들인지 확인을 해볼 필요가 있다는 것이다.

사실은 "위 초록색 문구들과 파랑색 문구들은 같은 결과 및 같은 의미를 내포하고 있다" 라고 말을 할 수는 없다. 왜 ?!

초록색 글씨의 Case1을 보게되면 "Card[1] + Card[1] + Card[1]" 이라고 적혀있다.

그런데 파랑색 글씨의 Case1을 보게되면 "Card[1] + 2장의 카드를 구매하는 경우" 라고 되어있다. 그럼 이 2개의 문장이 서로 같다고 가정한다면, 빨강색으로 표시된 2개의 문구가 서로 같은 결과값을 가져야 한다.

즉 ! " Card[1] + Card[1] = 2장의 카드를 구매하는데 드는 비용. " 이라고 말을 할 수 있어야 한다는 것이다.

글씨만 본다면 틀린 말은 아니다. 1장짜리 카드팩을 2개 사게 되면 결국 2장의 카드를 구매하는 경우니까, 결과적으로는 2장의 카드를 구매할 수 있을 것이다. 그런데 ! 굳이 이런 계산을 할 필요가 있냐에 대해서 생각을 해보자.

분명히 2장의 카드를 구매하는데 드는 '최대금액' 을 우리는 위에서 구해놨다. F[2] 라고 구해서 적어놓기까지 했다.

그런데 ! F[2]를 냅두고, 굳이 Card[1] + Card[1] 로 계산을 할 필요가 있을까 ?? 할 필요가 없다.

파랑색 글씨로 적어놨듯이, Case1은 Card[1] + 2장의 카드를 구매하는 경우인데, 지불해야 하는 금액을 최대금액으로 지불해야 한다면, Card[1]의 값을 바꿀 수는 없으니, "2장의 카드를 구매하는 경우"를 최대금액으로 만들어 주는것이 Case1에서 발생할 수 있는 가장 큰 금액이 된다는 것이다.

그래서 ! 위의 초록색 글씨와 파랑색 글씨를 이렇게 한번 바꿔보자.

Case1 : Card[1] + F[2]  |  Card[1] + 2장의 카드를 구매하는 데 지불해야 하는 최대금액

Case2 : Card[2] + F[1]  |  Card[2] + 1장의 카드를 구매하는 데 지불해야 하는 최대금액

Case3 : Card[3] + F[0]  |  Card[3] + 0장의 카드를 구매하는 데 지불해야 하는 최대금액

위와 같이 표현을 한다면, 초록색 문구들과 파랑색 문구들이 서로 같은 의미를 갖고 같은 표현을 하고 있다는 것을 더욱 확실하게 알 수 있고, 최대금액을 구해야 하기 때문에 보다 정확한 식이라고 말할 수 있다.

그럼 4장의 카드를 구매하기 전에, N장의 카드를 구매하려고 할 때, 비교해야 하는 방법들을 적어보자.

아마 이런 경우들이 발생할 것이다.

Case1 : Card[1] + F[N - 1]

Case2 : Card[2] + F[N - 2]

Case3 : Card[3] + F[N - 3]

......

CaseN : Card[N] + F[0]

이렇게 비교를 해서 가장 최대금액이 N장의 카드를 사는데 드는 최대금액이 될 것이다.

그럼 ! 위의 식이 옳게 적용이 되는지 4장, 5장의 카드에 적용시켜 보자. 다시 예시를 가져 오겠다.
카드팩의 가격 = { 1 , 4 , 2 , 7 , 3 }

현재까지 구한 가격 : F[1] = 1 , F[2] = 4 , F[3] = 5

F[4] 를 구하기 위해서 위의 식을 그대로 적용시켜보면

Case1 : Card[1] + F[3] = 1 + 5 = 6

Case2 : Card[2] + F[2] = 4 + 4 = 8

Case3 : Card[3] + F[1] = 2 + 1 = 3

Case4 : Card[4] + F[0] = 7 + 0 = 7

이 중 최댓값은 2번 Case인 8원이 된다.

마지막으로 정리해보자 !

N장의 카드를 사는데 지불해야 하는 최대금액을 구하기 위해서는 다음과 같은 경우들을 모두 비교해주면 된다.

1. 1장짜리 카드팩을 사는데 지불해야 하는 금액 + N - 1장의 카드를 사는데 지불해야 하는 최대 금액

2. 2장짜리 카드팩을 사는데 지불해야 하는 금액 + N - 2장의 카드를 사는데 지불해야 하는 최대 금액

3. 3장짜리 카드팩을 사는데 지불해야 하는 금액 + N - 3장의 카드를 사는데 지불해야 하는 최대 금액

.....

N. N장짜리 카드팩을 사는데 지불해야 하는 금액 + 0장의 카드를 사는데 지불해야 하는 최대 금액

이 부분을 코드로 나타내기 위해서 본인은 1차원 배열을 하나 사용해 주었다.

바로 int DP[] 라는 배열인데, DP[A] = B의 의미는 F[A] = B의 의미와 같다.

"A장의 카드를 사는데 지불해야 하는 최대금액은 B원입니다." 를 의미한다.

DP[N]의 값을 구하기 위해서는

Card[1] + DP[N - 1]

Card[2] + DP[N - 2]

Card[3] + DP[N - 3]

Card[4] + DP[N - 4]

...

Card[N] + DP[0]

의 값들을 비교해서 최댓값을 갖는 금액이 N장의 카드를 구매할 때, 지불해야 하는 최대금액이 된다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 1010
using namespace std;
 
int N;
int Card[MAX];
int DP[MAX];
 
int Max(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> Card[i];
}
 
void Solution()
{
    //DP[a] = b => a개의 카드를 갖기 위해서 지불해야 하는 최대금액은 b원입니다.
    DP[1] = Card[1];
    for (int i = 2; i <= N; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            DP[i] = Max(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;
}