알고리즘 :: 백준 :: DP :: 6603 :: 카드 구매하기2

문제

민규가 구매하려고 하는 카드의 개수 N과 카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최솟값을 구하시오.

문제접근

1. https://velog.io/@embeddedjune/백준-알고리즘-DP-11052-카드-구매하기 문제에서 최댓값을 구하는 목표가 최솟값을 구하는 것으로 변경되었다.
2. 단순히 max()함수를 min()함수로 변경하는 것이 답이 아니다. 초기값이 중요하다. 왜냐하면 초기값이 0으로 설정되어있으므로 min()함수를 써도 항상 답은 0이 나오기 때문이다. 따라서 초기값을 잘 설정해주는게 중요하다.
3. 이 문제에서 1,000개의 카드가 모두 10,000가격을 가진다면 최대값은 1,000 * 10,000이므로 초기값을 그 값으로 설정하면 된다.
4. 또는 초기값을 -1로 설정하고 min()함수를 사용하지 않는 방법도 있다.

코드

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

static int N = 0;
static vector<int> dp(1001, -1);

int solve(const vector<int>& card) {
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= i; ++j)
            if (dp[i] == -1 || dp[i] > dp[i - j] + card[j])
                dp[i] = dp[i - j] + card[j];
    return dp[N];
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> N;
    vector<int> card(N + 1);
    for (int i = 1; i <= N; ++i) cin >> card[i];

    cout << solve(card) << '\n';
}

또는

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

static int N = 0;
static vector<int> dp(1001, 1000*10000);

int solve(const vector<int>& card) {
    dp[0] = 0;
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= i; ++j)
            dp[i] = min(dp[i], dp[i - j] + card[j]);
    return dp[N];
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> N;
    vector<int> card(N + 1);
    for (int i = 1; i <= N; ++i) cin >> card[i];
    cout << solve(card) << '\n';
}

결과