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

문제 파악

동전 종류의 개수 N, 목표 금액 K
그리고 동전의 종류들이 주어졌을 때
최소 동전의 개수로 목표 금액을 만들어야 하는 문제이다.

어떻게 풀 수 있을까?

문제 조건을 잘 살펴보면

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

(i ≥ 2인 경우에 Ai는 Ai-1의 배수) 라는 말이 있다.

이는 즉 Ai로 표현할 수 있다는 것은 그 Ai의 작은 요소로도 표현할 수 있음을 의미하기에 그리디 알고리즘으로 풀 수 있음을 의미한다!

그렇기에 당장 큰 화폐단위부터 작은 화폐 단위순으로 순차적으로 쓸 수 있음이 보장된다.

만약 저 조건이 없고 무작위로 동전 종류가 주어졌다면 그리디 알고리즘은 쓸 수 없다.

해답 및 풀이

import sys
input = sys.stdin.readline

N, K = map(int,input().split())

coins = []
for _ in range(N):
    coins.append(int(input()))

# 정답 담을 그릇
count = 0

# coins가 오름차순이기 때문에 내림차순으로 정렬해준다.
sorted_coins = sorted(coins, reverse=True)

for c in sorted_coins:
    count += K // c # 카운트는 목표 금액을 현재 화폐단위로 나눈 값 (을 계속 저장해줌)
    K %= c # 목표 금액은 나누고 나머지로 계속 갱신

print(count)