백준 16194번 카드 구매하기 2 [C++]

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

16194번: 카드 구매하기 2

#문제 간단 정리

dp 를 쓰자

주의할건 dp 배열의 초기값을 높게 설정해 줘야 한다

최소값을 고르는거기 때문에 0이 설정되어 있다면 최소값으로 0이 선택되기 때문이다.

#전체 코드

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;


int main() {

    ios::sync_with_stdio(0); cin.tie(0);

    int n;
    cin >> n;
    vector<int> card(n + 1);
    vector<int> d(n + 1,123456789);
    for (int i = 1; i <= n; i++) {
        cin >> card[i];
    }
    d[0] = 0;
    d[1] = card[1];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <=i; j++) {
            d[i] = min(d[i], d[i - j] + card[j]);
        }
    }

    cout << d[n];

    return 0;
}

#코드 설명

이 문제는 동적 계획법(Dynamic Programming)을 사용하여 해결할 수 있는 문제입니다. 주어진 코드도 동적 계획법을 사용하여 문제를 해결하고 있습니다. 문제에서 요구하는 것은 주어진 카드 팩의 가격을 바탕으로 N개의 카드를 최소 비용으로 구매하는 방법을 찾는 것입니다.

주어진 코드의 주요 부분을 설명하겠습니다:

vector<int> card(n + 1);와 vector<int> d(n + 1,123456789);는 각각 카드 팩의 가격과 각 개수의 카드를 구매하는데 필요한 최소 비용을 저장하는 배열입니다.

d[0] = 0;와 d[1] = card[1];은 초기값 설정입니다. 0개의 카드를 구매하는데는 비용이 없고, 1개의 카드를 구매하는데는 card[1]의 비용이 듭니다.

이중 for문을 사용하여 각 개수의 카드를 구매하는데 필요한 최소 비용을 계산합니다. 여기서 d[i] = min(d[i], d[i - j] + card[j]);는 i개의 카드를 구매하는데 필요한 최소 비용을 구하는 식입니다. i-j개의 카드를 구매하는데 드는 최소 비용에 j개 카드 팩의 가격을 더한 값과 현재의 d[i] 값을 비교하여 더 작은 값을 d[i]에 저장합니다.

최종적으로 cout << d[n];을 통해 N개의 카드를 구매하는데 필요한 최소 비용을 출력합니다.