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

https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

---

카드 구매하기는 n이 최대 1,000이므로 백트래킹을 이용하면 시간 초과가 발생할 수 있습니다. 

카드 구매하기는 다이나믹 프로그래밍을 이용하여 해결할 수 있습니다.

 

다이나믹 프로그래밍의 테이블 d[i]는 카드 i개를 구매하기 위해 지불해야하는 금액의 최댓값으로 정의했습니다.

d[1]은 경우의 수가 하나이므로, d[1] = p[1]입니다.

 

돈을 최대한 많이 지불하여 n개의 카드를 구매하려면, 가성비가 가장 좋지 않은 카드의 개수 m개를 최대한 반복하여 구매한 후, 남은 카드도 최대한 비싸게 구매하면 됩니다. (단, m < n)

 

따라서, d[i]를 아래와 같이 정의할 수 있습니다. 

// 가성비가 가장 좋지 않은 카드를 반복하여 구매하고, 남은 카드도 최대한 비싸게 구매
d[n] = max(d[n], (n / i) * dp(i) + dp(n - i * (n/i)));

⚠️ 단, n개의 카드를 구매할 때, n개의 카드가 들어있는 카드팩 1개를 구매하는 것이 가장 비쌀 수 있으므로, 이 경우의 수도 고려해야합니다.

 

아래는 Top-Down 방식의 다이나믹 프로그래밍 코드입니다. 

#include <bits/stdc++.h>
using namespace std;
int p[1010], d[1010];   // d[i]는 카드 i개를 구매하기 위해 지불해야하는 금액의 최댓값
int n;

// Top-Down 방식의 다이나믹 프로그래밍
int dp(int n){  // 카드 n개를 구매하기 위해 지불해야하는 금액의 최댓값을 반환하는 함수
    if(d[n] != 0) return d[n];  // 이미 최댓값이 기록되어 있는 경우 해당 값 반환
    else{
        for(int i = 1; i < n; i++)  
            d[n] = max(d[n], (n / i) * dp(i) + dp(n - i * (n/i))); // 가성비가 가장 좋지 않은 카드를 반복하여 구매하고, 남은 카드도 최대한 비싸게 구매
        d[n] = max(d[n], p[n]); // n개의 카드가 들어있는 카드팩의 가격과 비교하여 최댓값 저장
        return d[n];
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++) cin >> p[i];    // 각 카드팩의 가격 입력 받음

    d[1] = p[1];  // 초기값 지정
    cout << dp(n) << "\n";  // 카드 n개를 구매하기 위해 지불해야하는 금액의 최댓값 계산
}

 

아래는 문제 풀이에 사용된 테스트케이스입니다.

4
1 4 97 4
-> 98

9 
10 30 1 1 1 1 1 1 1
-> 130