[백준/C++] 11052번: 카드 구매하기

문제

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

---

문제 요약

민규는 N개의 카드를 구매하려고 한다.

 

카드는 카드팩 구매를 통해 얻을 수 있다.

 

카드팩의 종류는 N가지가 있다.

- 1팩에 카드 1개가 있는 카드팩, 2개가 있는 카드팩, ... , N개가 있는 카드팩

 

카드가 i개 포함된 카드팩의 가격들이 주어졌을 때, 민규가 지불할 수 있는 금액의 최댓값을 출력한다.

---

코드

#include <iostream>
#include <algorithm>

using namespace std;

int N;

// arr[i]: i개의 카드가 들어있는 카드팩의 가격
int arr[1010];

// dp[i]: i개의 카드를 구매하기 위해 필요한 최대 가격
int dp[1010];

int dfs(int cnt) {
    if (cnt == 1) return arr[1];
    if (dp[cnt] != 0) return dp[cnt];

    // 카드 cnt개를 획득하기 위한 모든 가능한 경우의 수 탐색
    int res = 0;
    for (int i = 1; i <= cnt; i++) {
        res = max(res, arr[i] + dfs(cnt - i));
    }

    return dp[cnt] = res;
}

int main() {
    // 입출력 단축 코드
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;

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

    cout << dfs(N);
}

---

코드 설명

Top-Down Dynamic Programming을 이용하여 문제를 해결한다.

 

1. i개의 카드가 들어있는 카드팩의 가격을 arr[i]에 입력 받는다.

 

2. i개의 카드를 구매하기 위해 필요한 최대 가격을 저장할 dp 테이블을 정의한다.

 

3. Top-Down 재귀 방식을 이용하여 N개의 카드를 구매하기 위해 필요한 최대 가격을 탐색한다.

+ 이 때, 이미 DP 테이블을 이용해 이미 탐색한 경우는 바로 구한다.

 

4. cnt개의 카드를 얻기 위해 cnt개의 모든 경우의 수를 탐색한다.

(카드 1개가 들어있는 카드팩 구매, 카드 2개가 들어있는 카드팩 구매, ...)

 

5. 모든 경우의 수 중에서 최대 가격을 반환하고, 출력한다.

---

고찰

처음에는 Bottom-Up 방식의 백트래킹 방식으로 시도했는데, 시간 초과가 발생했다.

 

< 초기 코드 >

#include <iostream>
#include <algorithm>

using namespace std;

int N;

// arr[i]: i개의 카드가 들어있는 카드팩의 가격
int arr[1010];

int res = 0;

void dfs(int idx, int cost, int cnt) {
    // cout << idx << " " << cost << " " << cnt << "\n";
    if (cnt > N) return;
    else if (cnt == N) {
        res = max(res, cost);
        return;
    }

    for (int i = idx; i <= N; i++) {
        dfs(i, cost + arr[i], cnt + i);
    }
}

int main() {
    // 입출력 단축 코드
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;

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

    dfs(1, 0, 0);

    cout << res;
}

 

시간복잡도를 줄일 방법을 고민하다가, DP를 생각하게 되어 적용했다.