백준 알고리즘 11047번: 동전 0 [C++]

문제 출처: www.acmicpc.net/problem/11047

11047번: 동전 0

1. 코드

#include <iostream>

using namespace std;

int n, k, sum;
int arr[10];

int main(void)
{
	cin >> n >> k;
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	for (int i = n - 1; i >= 0; i--)
	{
		if (k >= arr[i])
		{
			sum += k / arr[i];
			k %= arr[i];
		}
	}
	cout << sum;
	return 0;
}

(실행)

2. 풀이

이 문제는 간단하다. 동전의 값을 저장한 뒤 제일 큰 동전의 값 중에서 모야할 값보다 작은 것이 있다면 해당 값을 나누면 그 몫은 동전의 수이며 나머지는 해당 동전으로 최대한 채운 뒤의 나머지 값이다. 그래서 해당 작업을 반복하면 간단하게 끝이 난다.

3. 느낀 점

정말 오랜만에 온전한 내 힘으로 풀었던 문제였던 것 같다. 그동안 다이나믹 프로그래밍 문제는 너무나도 어려웠는데 그리디 알고리즘은 아직 첫 문제라 쉬운것 같다.