C++ / 백준 / 14916 / 거스름돈

문제

 

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

14916번: 거스름돈

문제풀이

 

이 문제는 수학적으로도 풀 수 있지만 DP로도 풀 수 있어서 DP로 풀었다.

1부터 N까지 거스름돈 동전 개수를 나타내기 위한 won 벡터와,  2원, 5원 동전이 들어있는 coin벡터를 선언했다.

 

거슬러 줄 수 없으면 -1을 출력해야 되기 때문에 벡터를 -1로 초기화했다.

DP를 사용할 것이기 때문에 0원의 동전의 개수는 0으로 설정해 준다.

 

2원 동전부터 시작하여 2의 배수가 되면 2원을 뺀 금액의 동전의 개수+1을 한다.

5원 동전도 마찬가지로 5원부터 5원을 뺀 금액의 동전의 개수+1을 한다.

9원 같은 경우는 4원(2원 2개) + 5원(1개)처럼 채워진다.

 

코드

#include <iostream>
#include <vector>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int idx(0), idx2(0), N(0);
	cin >> N;
	vector<int>won(N + 1, -1);
	vector<int>coin = { 2,5 };

	won[0] = 0;

	for (idx = 0; idx < coin.size(); ++idx) {
		for (idx2 = 1; idx2 <= N; ++idx2) {
			if (idx2 >= coin[idx] && won[idx2 - coin[idx]] != -1) {
				won[idx2] = won[idx2 - coin[idx]] + 1;
			}
		}
	}

	cout << won[N];
}