문제 요약

[11047] 동전 0
동전의 종류가 오름차순으로 주어지고 동전들로 K값을 만들 때 필요한 동전의 최소 개수를 구해야 하는 문제

풀이 과정

다음 예제처럼 4200원을 만들기 위해서는 1000원 4개 + 100원 2개 => 총 6개의 동전이 필요함

값이 큰 동전부터 차례대로 살펴보며 사용해야 함

코드 (C/C++)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 10000
int main(void)
{
	int n, k; //동전의 수, 목표 금액
	int* coin; //동전의 종류를 저장할 배열 (내림차순으로)
	int cnt = 0; //필요한 동전 개수
	scanf("%d %d", &n, &k);
	coin = (int*)malloc(sizeof(int) * n);
	for(int i = n-1; i >= 0; i--)
	{
		scanf("%d", &coin[i]);
	}
	for (int i = 0; i < n; i++)
	{
		if (coin[i] <= k) //현재 동전을 이용하여 금액을 구성할 수 있다면 (ex. 1000원 <= 4200원)
		{
			cnt += (k / coin[i]); //목표값을 동전값으로 나눈 몫만큼 동전이 필요하고
			k = k % coin[i]; //목표값은 나눈 나머지 값으로 갱신
		}
		if (k == 0) //동전을 이용하여 금액을 모두 만들었다면 
		{
			break; //반복 종료
		}
	}
	printf("%d", cnt);
}

생각해보아야 할 점

동전이 배수 관계가 아닌 경우에는 그리디를 사용할 수 없음

• 문제에서 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수임 -> 작은 단위의 동전들을 종합하여 다른 해가 나올 수 없기 때문에 그리디가 보장이 됨
• 만약 800원을 맞춰야하고 화폐 단위가 500원, 400원, 100원이라면 => 500원 1개 + 100원 3개가 해답이 될 수 없음 (500원이 400원의 배수가 아님, 그리디로 풀 수 없음, 400원 2개가 해답임)