BOJ 11047번 동전 0

BOJ : https://www.acmicpc.net/problem/11047

github : https://github.com/junho0956/Algorithm/blob/master/11047/11047/%EC%86%8C%EC%8A%A4.cpp

 

동전 0 과 같은 문제는 1, 5, 10, 50, .. 과 같은 현재 한국의 동전형태와 같이 나오기 때문에 가능한 문제일 것입니다.

만약 동전이 12원짜리가 있다거나 했을 때는 동적계획법으로 풀어야 해결할 수 있습니다.

 

#include <iostream>
using namespace std;
 
int coin[10];
 
int main() {
    int N, K;
    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        cin >> coin[i];
    }
 
    int cnt = 0;
    while (K) {
        if (coin[N - 1] <= K) K -= coin[N - 1], cnt++;
        else N--;
    }
 
    cout << cnt;
    return 0;
}