[그리디 알고리즘] 동전 0

예제 입력 1

10 4200

1

5

10

50

100

500

1000

5000

10000

50000

예제 출력 1

6

예제 입력 2

10 4790

1

5

10

50

100

500

1000

5000

10000

50000

예제 출력 2

12

 

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

11047번: 동전 0

- 이 문제의 조건에서는 주어지는 동전이 Ai는 Ai-1의 배수라고 했으므로, 그리디 알고리즘을 사용하여 풀 수 있다.

- 만약, 위 조건이 없다면 그리디로 풀 수 없다.

반례) 1, 4, 5원 동전이 있고 12원을 만드려고 한다.

: 그리디) 5원 동전 2개 + 1원 동전 2개 = 4개

: 진짜 답) 4원 동전 3개 = 3개

 

#include <stdio.h>

constexpr int MAX_COUNT = 10;
int coins[MAX_COUNT];

int N, target;
int ans = 0;

int main(void)
{
	scanf("%d %d", &N, &target);

	for (int i = 0; i < N; i++)
	{
		scanf("%d", &coins[i]);
	}

	for (int i = N - 1; i >= 0; i--)
	{
		ans += (target / coins[i]);
		target %= coins[i];
	}

	printf("%d\n", ans);

	return 0;
}