[정글 알고리즘] - [하] 백준11047- 동전 0- 실버4

백준 · 그리디 · 동전 · 실버4

가장 큰 동전부터 최대한 사용하는 대표적인 그리디 동전 문제

문제 링크 바로가기

문제 한눈에 보기

목표	주어진 금액 k를 만들기 위한 최소 동전 개수 구하기
핵심 전략	가장 큰 동전부터 가능한 만큼 사용
풀이 방식	내림차순 정렬 + 그리디

핵심 1

동전이 큰 순서로 정렬되어 있으면 항상 큰 값부터 보는 것이 유리하다.

핵심 2

k // coin 으로 현재 동전 개수를 구한다.

핵심 3

남은 금액은 k % coin 로 갱신한다.

최종 코드

n, k = map(int, input().split())
coins = []
for _ in range(n):
    coins.append(int(input()))

result = 0
coins.sort(reverse=True)

for coin in coins:
    cnt = k // coin
    if cnt > 0:
        k %= coin
        result += cnt

print(result)

한 줄씩 설명

줄	코드	설명
1	n, k = map(int, input().split())	동전 종류 수와 목표 금액 입력.
2-4	coins.append(int(input()))	각 동전 가치 입력.
7	coins.sort(reverse=True)	큰 동전부터 보기 위해 내림차순 정렬.
9	cnt = k // coin	현재 동전으로 몇 개 사용할 수 있는지 계산.
10-12	if cnt > 0: k %= coin result += cnt	남은 금액 갱신 후 총 개수에 더한다.
14	print(result)	최종 최소 동전 개수 출력.

왜 그리디가 맞을까?

이 문제는 큰 단위 동전이 작은 단위 동전의 배수 구조를 이루기 때문에 큰 동전부터 최대한 쓰는 선택이 전체 최적해로 이어진다.

한 문장 정리

동전 0은 큰 동전부터 최대한 사용하는 그리디 전략이 그대로 정답이 되는 대표 문제다.