백준 11047번: 동전 0

[문제 링크]

11047번: 동전 0

---

이 문제같은 경우 메모이제이션을 활용한 동적계획법으로도 정답을 얻을 수 있을 것이다.

하지만 K의 최댓값이 100,000,000이고 동전의 가치가 1원부터 시작하기 때문에 최악의 경우 시간초과가 걸릴 것이 분명하다.

 

문제의 핵심은 입력으로 주어지는 조건에 있다.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

 

보다시피 Ai는 Ai-1의 배수이기 때문에 조합에 따라 K원을 만들지 못하거나, 만들 수 있는 경우로 나뉘지 않는다.

 

따라서, 가장 큰 가치의 동전부터 시작하여 동전의 가치가 K원보다 큰지 작은지 비교한 다음 작을 경우 K원을 동전의 가치로 나눈 몫을 동전 갯수에 누적시키고, 나머지를 가지고 다시 비교하는 것을 반복하면 최종적으로 K가 0이 되었을 때 누적된 동전 갯수가 곧 최소 갯수가 된다.

---

#include <iostream>
using namespace std;

int coin[10];

int Greedy(int N, int K, int cnt) // 재귀
{
	if (K == 0) return cnt;

	for (int i = N - 1; i >= 0; i--)
		if (K <= coin[i])
			return Greedy(N, K % coin[i], cnt + (K / coin[i]));
}

int Greedy2(int N, int K) // 비재귀
{
	int cnt = 0;

	for (int i = N - 1; i >= 0; i--)
	{
		if (K == 0) return cnt;

		if (K <= coin[i])
		{
			cnt += K / coin[i];
			K %= coin[i];
		}
	}

	return cnt;
}

int main(void)
{
	int N, K;
	cin >> N >> K;

	for (int i = 0; i < N; i++)
		cin >> coin[i];

	cout << Greedy(N, K, 0) << endl;

	cout << Greedy2(N, K) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 110 day