백준 BOJ 17212 - 달나라 토끼를 위한 구매대금 지불 도우미

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

17212번: 달나라 토끼를 위한 구매대금 지불 도우미

DP 알고리즘 문제.

dp[k]를 k원 계산을 할때 필요한 최소 동전의 개수로 정의하면

dp[k-a] 에서 a원어치 동전을 b개 지불하면

dp[k-a]+b = dp[k]가 되므로

dp[k] = min({dp[k-1], dp[k-2], dp[k-5], dp[k-7]})+1 이 된다.

해당 식을 그대로 적용해서 재귀문을 이용해 풀어도 되고

 

나는 바텀업 DP를 짰다.

입력에 들어올수 있는 수의 범위에 0이 있는것에 주의해주면 된다.

#include <bits/stdc++.h>
using namespace std;

int dp[123456] = {0};

int main(){
	for(int i=0; i<123456; i++) dp[i] = 998244353;
	
	dp[0] = 0;
	
	for(int i=0; i<=100000; i++){
		dp[i+1] = min(dp[i]+1, dp[i+1]);
		dp[i+2] = min(dp[i]+1, dp[i+2]);
		dp[i+5] = min(dp[i]+1, dp[i+5]);
		dp[i+7] = min(dp[i]+1, dp[i+7]);
	}
	
	int N;
	cin >> N;
	cout << dp[N];
	return 0;
}