백준(BaekJoon) 11047번 : 동전 0 - python 풀이

❓11047번 : 동전 0

📈 문제 요약

주어지는 동전 N종류를 활용해서 K를 만드는 데 필요한 최소 동전 개수를 구하면 되는 문제

🤨 접근법

그리디 알고리즘의 대표적인 문제인 동전 거스롬돈 문제와 같은 유형의 문제

가장 적은 동전의 수를 구해야 하므로 가장 큰 금액의 동전부터 활용해야 한다.

위와 같은 예제에서 4200을 만들기 위해 가장 큰 50000 동전부터 포함해본다. 하지만 50000 동전을 포함하는 순간 4200을 넘어선다.

• 50000 → 0

그 다음 동전인 10000 동전과 5000 동전도 마찬가지

• 10000 → 0
• 5000 → 0

그 다음 동전인 1000 동전은 4번 사용될 수 있다. 5번은 사용시 4200원을 넘어선다.

• 1000 → 4

1000 동전 4개가 4000원을 만들어 냈으므로 나머지 200원만 만들면 된다.

500 동전은 200을 만들어 내지 못한다.

• 500 → 0

100 동전 2개로 200을 만들어낼 수 있다.

• 100 → 2

총 4200원을 만들어내기까지 사용된 동전의 수는 1000원 4개와 100원 2개로 총 6개이다.

이와 같은 방식이 동전 거스름돈 문제에서의 그리디 알고리즘이다.

🔡 코드

import sys

input = sys.stdin.readline

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

coins = [int(input()) for _ in range(N)]
result = 0
for coin in reversed(coins):
    result += K//coin
    K %= coin
    if K == 0:
        break
print(result)

가장 큰 동전부터 활용하기 위해 동전 종류를 입력받은 후 reversed로 리스트를 뒤집어 사용했다. 해당 동전이 K에 몇 번 사용 가능한지를 구하기 위해 // 연산을 활용해 몫을 구하면 사용하게 되는 동전의 수가 되어 result에 더해줬다.

위 연산으로 얼마를 더 구해야하는지를 구하기 위해 %연산을 활용해 나머지를 K값으로 업데이트 해준다.

가장 큰 동전부터 반복하며, K가 0으로 업데이트 되는 순간 반복문을 탈출하여 불필요한 연산을 방지한다.