[백준] 11047 동전 0

📌문제 링크

11047 동전 0

💡 문제 풀이

입력 조건에서 동전의 가치 Ai에 대해 A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수라고 했으므로, 가장 큰 가치의 동전에서부터 개수를 계산하면 최적의 해를 보장할 수 있다.

예를 들어, 동전의 가치(화폐 단위)가 500원, 400원, 100원인 경우에 800원을 만들려면 최적의 해는 2(400 + 400)이지만, 그리디 알고리즘으로는 4(500 + 100 + 100 + 100)이 나오게 된다.
하지만 동전의 가치가 서로 배수 형태이기 때문에 가치가 큰 단위부터 계산하면 최적의 해를 보장할 수 있다.

📋코드

책 코드 참고했습니다

# 11047 동전 0
n, k = map(int, input().split())
coin = []
count = 0  # 동전의 개수를 저장할 변수

# 동전의 가치 입력받음
for i in range(n):
    coin.append(int(input()))

# 동전의 가치가 오름차순으로 주어지므로 뒤에서부터 계산
for i in range(n-1, -1, -1):
    count += k // coin[i]  # k원에서 현재 단위만큼 나눈 몫을 더함
    k %= coin[i]  # 나머지를 구해 다음 단위에서 계산함

print(count)