백준 14916번: 거스름돈 (C++)

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

14916번: 거스름돈

---

Solved By: Coin Change DP

 

처음으로 풀어본 DP, Coin Change 기법이었습니다. 자세한 설명은 코드에 주석으로 달아두었습니다.

#include <iostream>
#define MAX 100001
using namespace std;

int cache[MAX];

int main(){
    int n; cin >> n;
    
    int coin[2] = {2, 5};
    
    for(int d = 1; d <= n; d++){
        cache[d] = -1; // 만들 수 없는 경우를 위해 -1로 assign
        for(int c = 0; c < 2; c++){ // coin의 index
            if(coin[c] <= d){
                // d원을 만들 때, 소모되는 동전들은 모두 d보다 작거나 같아야 함
                // 그렇기에 coin[c] <= d라는 조건을 통과해야 함.
                
                if(cache[d - coin[c]] < 0) continue;
                // d - coin[c]원을 만드는데에 있어서 방법이 없다면
                // 해당 coin[c]를 더한다 해도 d가 만들어지지 않는다는 소리다.
                // 즉, continue 시켜야 함.
                // 이 조건을 통과했다면 d - coin[c]원을 만들 수 있다. 라는 뜻.
                // 즉, d - coin[c]원에 coin[c]원을 더하여 d원을 만들 수 있다는 뜻
                
                if(cache[d] < 0) cache[d] = cache[d - coin[c]] + 1;
                // 위의 조건들을 다 통과했다는 건 coin[c]원을 더했을 때
                // d원이 만들어진다는 소리다.
                else if(cache[d - coin[c]] + 1 < cache[d]){
                    cache[d] = cache[d - coin[c]] + 1;
                }
                // 다른 동전들을 탐색하면서 더 최적의 값을 찾아내는 과정에
                // 최적의 값을 갱신하는 코드다.
            }
        }
    }
    
    cout << cache[n];
    return 0;
}