거스름돈( BOJ 14916 )

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

14916번: 거스름돈

 

문제 파악하기

2원과 5원을 사용해서 N원을 만드는 방법 중 동전을 가장 적게 사용하는 방법을 찾는 문제입니다. 아쉽게도 5원부터 먼저 사용하는 방법으로는 문제를 풀 수 없습니다. 예를 들어 6원 같은 경우, 5원을 먼저 사용하는 방법으로는 해답을 찾을 수 없습니다. 따라서, 그리디 방식이 아닌 모든 경우를 고려하는 동적 프로그래밍이 필요합니다.

 

문제 해결하기

N원을 만들기 위해서는 2가지 조건 중 하나만 만족하면 됩니다. (N-2)원을 만들 수 있거나 (N-5)원을 만들 수 있으면 됩니다. 따라서, 우리는 0원부터 N원까지 다음 점화식을 사용해서 최소 동전의 개수를 구하면 됩니다.

dp[i] = min(dp[i-2], dp[i-5]) + 1

 

다만, 나올 수 없는 경우도 있으니 dp[i]의 초깃값을 충분히 큰 값으로 설정한 다음, dp[i-2]와 dp[i-5]의 값을 비교하면 됩니다. 문제를 해결하는 소스코드는 다음과 같습니다.

 

소스코드

#include <stdio.h>
#include <algorithm>
#define NMAX 100010
using namespace std;
 
int N;
int dp[NMAX];
 
int main() {
    scanf("%d", &N);
 
    dp[0] = 0;
    for(int i=1;i<=N;i++) {
        dp[i] = NMAX;
 
        if(i>=2) dp[i] = min( dp[i], dp[i-2]+1 );
        if(i>=5) dp[i] = min( dp[i], dp[i-5]+1 );
    }
 
    if(dp[N] == NMAX) printf("-1");
    else printf("%d", dp[N]);
}

후기

기본적인 bottom-up방식의 동적 프로그래밍을 연습할 수 있는 문제입니다. 동적 프로그래밍을 시작하는 사람들에게 추천할 만한 문제입니다.