C++ 백준 14916번 : 거스름돈

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

14916번: 거스름돈

문제

춘향이는 편의점 카운터에서 일한다.

손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오.

예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다.

입력

첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다.

출력

거스름돈 동전의 최소 개수를 출력한다. 만약 거슬러 줄 수 없으면 -1을 출력한다.

---

풀이

2원만 가지고 있을 경우 - > 2,5원 둘 다 가지고 있을 경우로 dp를 이용해서 풀었다.

 

• 2원만 가지고 있을 경우

	1	2	3	4	5	6	7	8	9
2원	-1	1	-1	2	-1	3	-1	4	-1
2원, 5원

거스름돈%/2 해서 나머지가 0이면 몫을 답으로 하고 0이 아니면 -1을 넣는다.

 

• 2원, 5원 둘 다 가지고 있을 경우

	1	2	3	4	5	6	7	8	9
2원	-1	1	-1	2	-1	3	-1	4	-1
2원, 5원	-1	1	-1	2	1	3	2	4	3

if 5원으로 나누어지면 몫이 동전의 최소 개수 

else 두번째 행에서 5원을 뺀 값을 보고 -1이면 다시 돌아와 바로 위의 값, -1이 아니면 그 값+1 을 해주면 된다.

 

예를 들어 거스름돈이 6원일 때 5원을 빼면 1원이 남는데 그 값이 -1이 이므로 첫번째 행의 값인 3을 들고 온다. ( 2원 3개를 준 경우)

거스름돈이 7원일 경우 5원을 빼면 2원이 남는데 그 값이 -1이 아니므로 그 값에 +1을 해준다.( 2원, 5원 하나씩 준 경우)

---

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int dp[2][100001] = { 0 }; // 0 : 2원, 1: 5원
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int num; cin >> num;
	dp[0][1] = -1;
	dp[1][1] = -1;
	for (int i = 2; i <= num; i++) { // 2원만 가지고 있을 경우
		if (i % 2 == 0) { 
			dp[0][i] = i / 2;
		}
		else {
			dp[0][i] = -1; // 거슬러 줄 수 없는 경우
		}

		if (i <= 5) { // 2,5원 둘 다 가지고있는데 거스름돈이 5원보다 작거나 같은 경우
			dp[1][i] = dp[0][i]; // 
		}
	}

	for (int i = 5; i <= num; i++) {
		if (i % 5 == 0) { // 5원가지고 나눠질 경우
			dp[1][i] = i / 5;
		}
		else {
			if (dp[1][i - 5] == -1) {
				dp[1][i] = dp[0][i];
			}
			else {
				dp[1][i] = dp[1][i - 5]+1;
			}
		}
	}
	cout << dp[1][num] << '\n';

}

 

다시 보니 그리디로 5원으로 최대한으로 지급한 후에 나머지 거스름돈을 2원으로 나눌 수 있다면 "5원으로 나눈 몫 + 나머지 거스름돈을 2원으로 나눈 몫" 이 정답이고 2원으로 못 나누면 -1로 쉽게 풀 수 있다는 것을 확인,,, 이런 문제보면 반사적으로 dp 떠올리는 버릇 안좋아 ~~ 쉽게 쉽게 풀자!