11047번: 동전 0 (7 / 31) - 실버 4

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

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

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

예제 입력 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

코드

# n: 동전의 개수  10개
# k: 만들려는 가치의 합  4200
n, k = map(int, input().split())

coins = []
# 동전의 합
result = 0

for i in range(n):
    x = int(input())  # 1 5 10 50 100 500 1000 5000 ...
    coins.append(x)

# 내림차순으로 변경하여 큰 수가 먼저 오도록 함
coins.sort(reverse=True)

for coin in coins:  # 50000 10000 5000 1000 500 ...
    # k가 coin보다 크거나 **같을 경우**에 실행 -> k = 5000 coin = 5000 -> result = 1
    if k >= coin:
        result += k // coin
        k = k % coin

print(result)

코드 풀이

1. 입력으로 들어오는 코인을 list에 추가하고 reverse=True 를 하여 내림차순으로 변경
   • 큰 동전부터 나누기 위해 이와 같이 작업
   • coins = [int(input()) for _ in range(n)] 이렇게 coin을 list comprehension으로 한 줄로 받을 수 있음
   • coins.sort(reverse=True)로 리스트를 내림차순으로 정렬한다.
2. 동전의 가치가 현재 금액 k보다 작다면 나눌 수 없음
   • 따라서 k가 coin 보다 크거나 같을 경우에만 로직을 수행한다.
   • k와 coin이 같을 경우를 포함하기 위해 부등호를 >= 으로 작성 - 이부분 때문에 한 번 틀림
3. k를 coin으로 나눈 몫은 result에 더하고 나머지를 다시 k에 전달한다.

핵심 포인트

• 그리디 알고리즘: k를 만들기 위한 동전 개수를 최소화 해야 함
• 내림차순으로 설정하여 큰 수부터 나눌 수 있도록 함
• k가 coin보다 크거나 같을 경우에만 나눌 수 있으므로 조건을 k >= coin 으로 설정한다.