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

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

( 문제 바로가기 )

[ 문제를 다시 푸는 과정에서 보다 구체적이고 상세한 설명으로 이 문제를 다시 포스팅 하였습니다.

  아래의 글을 참고하셔서 풀이하셔도 무관하지만 , 더욱 구체적이고 상세한 설명을 원하시는 분들은

  아래의 링크를 이용해주시면 감사하겠습니다.

  [ 백준 카드구매하기(11052) 풀이 보러가기 ] ]

[ 문제설명 ]

- 입력으로 구매하고자 하는 카드의 갯수와, 각 카드팩의 가격이 주어진다. 

- 카드팩은 카드가 1개가 포함되 있는카드부터 최대 N개가 포함되어 있는 카드팩으로 주어진다.(P1, P2, P3,... PN)

- 비싼 카드팩일 수록 좋은 카드가 들어있다고 가정하고, 구매하고자 하는 카드의 갯수를 살 때, 최대 비용으로 살 때

  그 최대 비용을 출력시키면 된다.

[ 문제풀이 ]

1) 카드팩의 가격을 저장해놓는 Arr배열과 최댓값을 관리하는 DP배열을 사용했다.

2) Arr[a] = 카드 a개의 가격 , DP[a] = a개 카드를 구매했을 때의 최대 비용을 의미한다.

3) 본인은 Arr배열을 1번 Index부터 사용했으므로 DP[0] = Arr[0] = 0이 된다.

4) 이 문제는 카드 N개를 구매할 때의 최대비용을 구해야 하므로, 마지막에 1개짜리 카드팩을 구매하는 경우를 생각해보자.

   마지막에 1개짜리 카드팩을 구매한다고 가정하면, 그 전에서 N-1개의 카드를 구매해야 하고, 이를 식으로 나타내면

   DP[N-1] + Arr[1] 이 된다. N-1개를 구매했을 때의 최대비용과 1개를 구매했을 때의 가격, 즉 총 N개를 구매한 가격이

   나오게 된다.

   마지막에 2장짜리 카드팩을 사는 것을 고려해보면, DP[N-2] + Arr[2]가 된다.

   마지막에 N장짜리 카드팩을 사는 것을 고려해보면, DP[N-N] + Arr[N]이 되게 된다.

   이 문제는, 최대비용을 구해야 하므로, 마지막에 카드를 1장 사는 것 부터 최대 N장 사는 것 까지 모두 다 고려해서

   비교해 주어야 한다.

5) 따라서, 위의 말을 토대로 점화식을 도출해본다면 DP[N] = DP[N] vs (DP[N-a] + Arr[a]) 가 된다.

6) 위의 점화식을 토대로 코드를 구현하면 된다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 1000 + 1
using namespace std;
 
int N;
int Arr[MAX];
int DP[MAX];
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> Arr[i];
    }
}
 
void Solution()
{
    // DP
    DP[0] = Arr[0] = 0;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            DP[i] = Bigger(DP[i], DP[i - j] + Arr[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;
}