[백준] 17212번 - 달나라 토끼를 위한 구매대금 지불 도우미 (C++)

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

 

 

문제

달나라 토끼들이 사용하는 화폐는 동전뿐이다. 동전의 종류는 1원, 2원, 5원, 7원 이렇게 4종류가 있다. 물건을 사고 동전으로 계산을 하는데 동전의 개수가 최소가 되도록 지불하지 않는 것은 불법이다. 예를 들어, 17원을 지불할 때 7원짜리 동전 1개와 5원짜리 동전 2개로 지불해야 합법이고, 7원짜리 동전 2개와 2원짜리 동전 1개, 1원짜리 동전 1개로 지불해도 17원이 되지만, 총 동전의 개수가 4개가 되어 최소 개수가 아니므로 불법이다.

지불 금액을 입력받아 합법이 되는 동전 개수를 출력으로 내어주는 프로그램을 작성해보자.

 

 

 

입력

첫 번째 줄에 달나라 토끼가 지불해야하는 금액 N(0 ≤ N ≤ 100,000)이 주어진다.

 

 

 

출력

첫 번째 줄에 달나라 토끼가 합법적으로 낼 수 있는 동전의 개수를 출력한다.

힌트

지불 금액	합법 지불	불법 지불(예)
12원	7원 x 1개 + 5원 x 1개	5원 x 2개 + 2원 x 1개
17원	7원 x 1개 + 5원 x 2개	7원 x 2개 + 2원 x 1개 + 1원 x 1개
21원	7원 x 3개	7원 x 2개 + 5원 x 1개 + 2원 x 1개

 

 

 

풀이과정

해당문제도 dp로 접근해서 풀 수 있었다.

문제에서 제공하는 동전에 최대값은 7원이라 0 ~ 7원의 경우 나오는 동전의 수를 모두 구하고 7원 이상의 값들은
dp(coin - 7) dp(coin - 5) dp(coin - 2) dp(coin - 1) 중 가장 작은 값을 구하고 그 값에 + 1을 해주는 형식으로 문제풀이를 진행하였습니다.

 

 

 

code

#include <iostream>
#include <algorithm>

int		f[100001];

int		dp(int coin)
{
	if (coin == 0) return (0);
	if (coin == 1) return (1);
	if (coin == 2) return (1);
	if (coin == 3) return (2);
	if (coin == 4) return (2);
	if (coin == 5) return (1);
	if (coin == 6) return (2);
	if (coin == 7) return (1);
	if (f[coin]) return (f[coin]);
	int min = std::min(std::min(std::min(dp(coin - 7), dp(coin - 5)), dp(coin - 2)), dp(coin - 1)) + 1;
	return (f[coin] = min);
}

int		main(void)
{
	int n;
	
	std::cin >> n;
	std::cout << dp(n);

	return (0);
}

 

후기

머리로는 이해가되지만 어떻게 점화식을 세워야할지 은근 고민을 많이했던 문제였던 거 같다.

수학적인 개념을 조금 더 공부를 많이해야할 거 같다.