동전 2

백준 2294번: 동전 2

아이디어

Dp테이블에 해당 금액을 만드는데 필요한 동전의 최소 개수를 기록한다. 1번 동전부터 N번 동전까지의 금액을 각각 S(1) ~ S(N)이라 하면, N번째 동전까지 사용해서 K원을 만드는데 필요한 동전의 최소 개수는 N-1번째 동전까지 사용해서 K원을 만드는 경우의 수와 N번째 동전까지 사용해서 K-S(N)원을 만드는 경우의 수에 1을 더한 값(K-S(N)원을 만들고 S(N)원짜리 동전을 하나 더 쓰면 된다)중 더 작은 경우이다.

코드

#include <bits/stdc++.h>

using namespace std;

int arr[101][10001];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    queue<int> q;
    int n, k;
    cin >> n >> k;
    while (n--) {
        int x;
        cin >> x;
        q.push(x);
    }
    
    fill(&(arr[0][0]), &(arr[0][0])+101*10001, 100000);
    
    for (int i = 0; i < 101; i++) {
        arr[i][0] = 0;
    }
    
    int t, s = 1;
    while (!q.empty()) {
        t = q.front();
        q.pop();
        for (int i = 1; i <= k; i++) {
            arr[s][i] = arr[s-1][i];
            if (i >= t) {
                arr[s][i] = min(arr[s][i], arr[s][i-t] + 1);
            }
        }
        s++;
    }
    
    if (arr[s-1][k] == 100000) cout << -1;
    else cout << arr[s-1][k];
   
    return 0;
}

여담

int 범위 조심. INT_MAX에다가 1을 더해서 INT_MIN이 되어버렸다..
INT_MAX에 1을 더했는데 왜 INT_MIN이 되냐고? 너는 공부좀 더 해야겠다..
또 배열을 초기화할 때 2차원 배열이라 포인터 연산이 좀 헷갈린다. 조심하도록.