[Baekjoon] 11047 : 동전 0 - python

문제

준규가 가지고 있는 동전은 총 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

---

풀이

문제를 보자마자 전형적인 그리디 유형이라는 생각이들었다.

그렇기 때문에 가장 높은 화폐부터 나누어가면 된다고 생각했다.

우선 배열로 동전값을 받은 후 sort를 통해 가장 높은 동전으로 정렬을 수행한다. 

이후 높은 화폐부터 나누어 가고 몫은 동전 개수에, 나머지는 다음 동전으로 연산을 해나간다.

추가로 나누기 전에 화폐가 k보다 클 경우에는 의미가 없으므로 조건문을 하나 추가했다.

 

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

# 높은 동전 순으로 정렬
coins.sort(reverse=True)

result = 0

for coin in coins:
    if k == 0:
        break
    if k >= coin:
        count, remain = divmod(k, coin)
        # 몫은 개수에, 나머지 값은 본래 k값에 할당
        result += count
        k = remain

print(result)