[백준] 14916 거스름돈 (DP)

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

14916번: 거스름돈

 

 

[풀이]

 

쭉 경우의 수를 적어보다보니 규칙이 보였다.

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

DP[2] = 1, DP[5] = 1, DP[4] = 2

 

계산을 할 수 없는 경우들이 존재하는데 우리는 min 함수를 사용하기 때문에

계산을 할 수 없는 경우를 고려하려면 초기에 DP 함수를 987654321 로 초기화를 해주어서 계산이 가능한지 아닌지 판별하면 된다.

 

사실  1~100000 의 수에서 거슬름돈을 줄 수 없는 경우는 1과 3뿐이다.

하지만 위의 공식으로 돌리다보면 1, 3 을 큰 수로 설정 해두지 않으면 dp[1] , dp[3] 을 가져다쓰기 때문에 실패로 뜬다. 

min(), max() 를 사용할 때는 기본적으로 각각 987654321, -1(or -987654321) 로 설정해두는 것을 잊지말자

 

#include <iostream>
#include <algorithm>
using namespace std;
int n;
int dp[100001];

void dynamic() {
	dp[2] = 1; dp[4] = 2;
	dp[5] = 1; 

	for(int i=6; i<=n; i++) {
		dp[i] = min(dp[i-5], dp[i-2]) +1;
	}
}

int main() {
	scanf("%d", &n);

	for(int i=0; i<=n; i++)
		dp[i] = 987654321;

	dynamic();

	int ret = dp[n];

	if(ret >= 987654321)
		printf("-1\n");
	else
		printf("%d\n", ret);

}