[알고리즘] 백준 카드구매하기 11052 DP 최댓값

안녕하세요, 감자코딩에 감자개발자입니다.

이번에 살펴볼 알고리즘 문제는 백준알고리즘 11052번 카드 구매하기 문제입니다.

이 역시도 DP관련 문제인데요, 하지만 다른점이 하나 있습니다.

이번 문제에서는 카드의 최대값을 구하는 문제입니다. 

지금 까지 포스팅한 DP문제들은 해당하는 경우의 수들을 구하는 문제였지만, 이번 문제는 한번 더 생각해야할 요소가 있습니다.

바로 들어가겠습니다 :)

1. 문제

카드 구매하기 성공

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율

1 초 256 MB 16161 9472 7020 59.036%

문제

요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.

PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.

전설카드

레드카드

오렌지카드

퍼플카드

블루카드

청록카드

그린카드

그레이카드

카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.

민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다.

예를 들어, 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값은 10원이다. 2개 들어있는 카드팩을 2번 사면 된다.

P1 = 5, P2 = 2, P3 = 8, P4 = 10인 경우에는 카드가 1개 들어있는 카드팩을 4번 사면 20원이고, 이 경우가 민규가 지불해야 하는 금액의 최댓값이다.

마지막으로, P1 = 3, P2 = 5, P3 = 15, P4 = 16인 경우에는 3개 들어있는 카드팩과 1개 들어있는 카드팩을 구매해 18원을 지불하는 것이 최댓값이다.

카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램을 작성하시오. N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능하다. 즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다.

입력

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)

둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

출력

첫째 줄에 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최댓값을 출력한다.

예제 입력 1 

4

1 5 6 7

예제 출력 1 

10

예제 입력 2 

5

10 9 8 7 6

예제 출력 2 

50

예제 입력 3 

10

1 1 2 3 5 8 13 21 34 55

예제 출력 3 

55

예제 입력 4 

10

5 10 11 12 13 30 35 40 45 47

예제 출력 4 

50

예제 입력 5 

4

5 2 8 10

예제 출력 5 

20

예제 입력 6 

4

3 5 15 16

예제 출력 6 

18

2. 문제 해결 방법

1) 총 N개의 카드팩 형태가 존재, 카드팩을 구매하는데 있어서의 최대값을 구하는 문제가 요점입니다. N은 카드의 종류, P는 카드의 가격입니다. 따라서, 카드를 구매하는데에 있어서 최댓값을 구하면 되겠습니다. 결국 DP문제 입니다. 

왜 DP문제라고 생각을 했을까요?

 일단 카드 종류가 4가지라고 예를 들어보겠습니다. 

카드의 종류마다 각각의 가격이 다릅니다. 

예를 들어, 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값은 10원이다. 2개 들어있는 카드팩을 2번 사면 된다.

P1 = 5, P2 = 2, P3 = 8, P4 = 10인 경우에는 카드가 1개 들어있는 카드팩을 4번 사면 20원이고, 이 경우가 민규가 지불해야 하는 금액의 최댓값이다.

마지막으로, P1 = 3, P2 = 5, P3 = 15, P4 = 16인 경우에는 3개 들어있는 카드팩과 1개 들어있는 카드팩을 구매해 18원을 지불하는 것이 최댓값이다.

이와 같이 카드팩의 가격에 따라 최댓값이 달라지는것을 볼 수 있습니다.  결국 모든 카드팩의 가격을 비교하여 가장 높은 최댓값을 구해내야하기 때문에 DP문제를 떠올리셔야합니다.

쓰앵님들은 할 수 있습니다. 죄송합니다...

따라서, 큰 문제를 작은 문제로 분할 할 수 있겠지요?

즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다. 이러한 조건이 있습니다. 

만약 4개의 카드를 얻고 싶다면 

4개의 카드 팩에서 (P1 = 3, P2 = 5, P3 = 15, P4 = 16)카드 팩이 있으면 비용의 최대값을 비교하여 구해야합니다

P3의 카드팩 1개와 P1의 카드팩 1개를 구매하게 된다면 18원의 최댓값을 구할 수 있게 될 것입니다. 큰 문제를 작은문제로 분할 시켜 문제를 푸는것입니다.

간단히 말해 : 

카드 1개를 P[1]에 구매 -> 남은 카드의 수 i-1 -> P[1] + D[i-1]

카드 2개를 P[2]에 구매 -> 남은 카드의 수 i-2 -> P[2] + D[i-2]

카드 3개를 P[3]에 구매 -> 남은 카드의 수 i-3 -> P[3] + D[i-3]

..

..

..

카드 N개를 P[N]에 구매 -> 남은 카드의 수 i-N -> P[N] + D[i-N] 

결국 N개의 카드를 넘어 갈 수 없다는 말입니다.

4개의 카드를 할때, 

하나의 카드를 3개짜리를 구매하고,2개 짜리를 구매 없다는 말입니다.

결국 1<= J <= I 라는 범위가 성립하게 됩니다.

밑에 그것들을 코드로 표현 해보겠습니다.

3. 코드 리뷰

//

//  카드 구매하기.cpp

//  beakjoon_algorithm

//

//  Created by kgh on 13/04/2019.

//  Copyright © 2019 kgh. All rights reserved.

//

#include <stdio.h>

#include <iostream>

#include <vector>

using namespace std;

vector<int> p(10001);

int dp[1001];

int main(void){

    

    int n;

    cin >> n;

    // n개 까지의 가격을 입력받는다.

    for(int i=1; i<=n; i++){

        cin >> p[i];

    }

    // n개 만큼의 값을 입력받고 i-j까지의 수를 넘어갈 수 없으므로, max를

    // i-j까지 p값을 더해나가면서 이용하여 최댓값을 구해준다.

    // 결국 최종 n의 값에 최대값이 들어가있는것을 확인 할 수 있다.

    

    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;

}

코드를 한번 잘 살펴보시고, 천천히 이해하면서 감을 익히시길 바랍니다.

처음에 DP접근 하는것에 있어서 제가 포스팅해왔던 방법과 살짝 다르기 때문에 

직접 그림을 그려보시면서 고민해보시길 바랍니다.

차근차근 하나씩 풀어보시다보면 감이 잡힐 것이라고 믿습니다.

이상 감자코딩에 감자개발자였습니다.

잘못된 부분이 있다면 댓글을 남겨주세요. 피드백은 사랑입니다 

공감 꾸욱 하나 눌러주세요