[BOJ 2294 // C++] 동전 2

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2294번 문제인 동전 2이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/2294

2294번: 동전 2

이 문제는 주어진 액수의 동전을 개수 제한없이 최대한 적은 개수로 사용하여 목표 금액을 만들어야 한다.

이를 위해, 각 동전이 들어올 때마다 목표금액 이하의 금액들에 대하여 만들 수 있는 최소 동전 개수를 계속 갱신해나가면 문제를 해결할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <cmath>
using std::cin; using std::cout;
using std::min;

int total[10001];

int main()
{
    int N, K; cin >> N >> K;
    int coin, index;
    for (int i = 0;i < N;i++) {
        cin >> coin; index = 0;
        while (index + coin <= K) {
            if (total[index] != 0 or index == 0) {
                if (total[index + coin] == 0) total[index + coin] = total[index] + 1;
                else total[index + coin] = min(total[index] + 1, total[index + coin]);
            }
            index++;
        }
    }
    if (total[K] == 0) total[K] = -1;
    cout << total[K];

    return 0;
}