[백준 C++] 11047 : 동전 0

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

그리디 알고리즘을 사용한 실버4 문제이다.

동전의 가치를 오름차순으로 입력한 뒤, 가장 최소한의 동전을 사용하여 K의 합을 만들면 문제이다.

처음에 어떻게 해야할지 막막할 수 있지만, 생각해보면 간단한 문제이다.

K값보다 작거나 같은 가치의 동전을 먼저 사용하고, 나머지는 먼저 사용한 동전보다 낮은 가치의 동전을 사용해서 다시 메꿔주는 작업을 반복하면 된다.

#include <iostream>

int main()
{
	int N, K;
	int array[10];
	int answer = 0;

	std::cin >> N >> K;

	for (int i = 0; i < N; i++)
	{
		std::cin >> array[i];
	}

	for (int i = N - 1; i >= 0; i--)
	{
		if (array[i] <= K)
		{
			while (1)
			{
				K -= array[i];

				answer++;

				if (array[i] > K)
					break;
			}
		}
		else if (K == 0)
			break;
	}

	std::cout << answer;

	return 0;
}