[백준/C++] 14916 거스름돈

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

14916번: 거스름돈

문제요약

거스름돈 금액이 입력으로 주어지고, 5원과 3원으로 해당금액을 만들 때, 만들수 있으면 동전의 최소 개수를, 만들 수 없으면 -1을 출력

문제해결

일단 5원을 가장 많이 사용하고 싶다고 생각할 수 있다.
예를 들어 23원을 계산한다고 했을 때, 5x4 + 3이 되는데 이는 안되므로 5x3 + 8이 된다.
이를 좀 더 바꿔서 dynamic programming을 적용시킨다고하면, 23은 5를 일단 하나 사용하고, 나머지 18(=23-5)을 만들수  있는 방법에 1을 더한다고 생각할 수 있다.
따라서 dp[i]를 금액 i에 대한 동전 최소개수라고 하자.

금액 n의 최소동전개수를 계산하여 dp배열에 저장하는 함수를 calc(n)이라고 하면, cal()내부에서는 calc(n-5)의 값을 계산한다. calc(n-5)가 계산되지 않는다면 calc(n-2)를 계산한다.
calc(n)의 초기조건은, n이 음수가되거나 1이면 -1(계산안됨)을 리턴한다.
dp배열은 -1로 초기화하고 dp[0]=0, dp[2]=1, dp[5]=1을 넣어주고 시작한다.

코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> mem(100001, -1);

int calc(int N){

    if(N<0 || N==1) return -1;
    if (mem[N] != -1) return mem[N];

    int change5 = calc(N-5);
    if (change5 == -1){
        int change2 = calc(N-2);
        if(change2 != -1) mem[N] = change2 + 1;
    }
    else{
        mem[N] = change5+1;
    }

    return mem[N];
}

int main(){
    mem[0] = 0;
    mem[2] = 1;
    mem[5] = 1;
    int change;
    cin >> change;
    cout << calc(change);
}