2-6. DP [BOJ 11052번]

1. 관련 문제 🎯

문제 : 백준 11052 카드 구매하기♣️
난이도 : 실버 1

2. 문제 소개 🧩

1️⃣ 카드는 카드팩의 형태로만 구매할 수 있다.
2️⃣ 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.
3️⃣ 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다.
4️⃣ 카드가 i개 포함된 카드팩의 가격은 Pi원이다.
5️⃣ N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능하다.
6️⃣ 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다.

ex) 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우

• 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값은 10원이다.
• 2개 들어있는 카드팩을 2번 사면 된다. (P2를 2개 구입)

3. 문제 풀이 🖌️

DP에서는 점화식을 찾는 것이 가장 중요하다!!
따라서, 1개의 카드를 구매할 때부터 N개의 카드를 구매할 때의 최대 비용을 나열해보면서 규칙을 찾아본다 🔥

• ☝️ P[i]는 i개의 카드가 들어있는 카드팩의 가격을 의미한다.
  (이때, P[i]는 입력값으로 주어진다.)
  F[i]는 i개의 카드를 구입하기 위한 최대 비용을 의미한다.
  
• 따라서, 다음과 같은 규칙을 발견할 수 있다!

3-1. cards[i]를 입력받고, dp[i]배열을 0으로 초기화한다.

• 위에서 정의한 F[i] 배열은 dp[i] 배열을 의미하며, P[i]는 cards[i] 배열을 가리킨다.

int cards[N+1];
int dp[N+1];

for(int i=1; i<=N; i++){
	cin>>cards[i];
	dp[i] = 0;
}

3-2. dp[i] 배열을 채운다.

• 이때, dp[1]은 위의 예시처럼 P[1]을 의미하기 때문에 따로 for문을 사용하지 않고, dp[1] = cards[1]을 작성해준다.
• 그리고 발견한 규칙을 적용하여 해당 i개의 카드의 최대값을 max를 사용하여 구해준다.

dp[0] = 0;
dp[1] = cards[1];

for(int i=2; i<=N; i++){
	for(int j=1; j<=i; j++){
		dp[i] = max(dp[i], cards[j]+dp[i-j]);
    }
}

4. 전체 코드 🔑

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    std::ios::sync_with_stdio(false); 
    cin.tie(NULL); cout.tie(NULL);

   int N = 0;
   cin>>N;
    
   int cards[N+1];
   int dp[N+1];

   for(int i=1; i<=N; i++){
        cin>>cards[i];
        dp[i] = 0;
   }

    dp[0] = 0;
    dp[1] = cards[1];

    for(int i=2; i<=N; i++){
        for(int j=1; j<=i; j++){
            dp[i] = max(dp[i], cards[j]+dp[i-j]);
        }
    }
    cout<<dp[N]<<"\n";
}

5. 결과 🏆