[백준] 11047 동전 0 (Python 파이썬)

www.acmicpc.net/problem/11047

11047번: 동전 0

문제 설명

N종류의 동전으로 K원을 만들 때, 동전 개수의 최솟값을 구하는 문제이다.

---

풀이 과정

먼저 coin 리스트에 코인들을 오름차순으로 입력받게 되는데, 가장 적은 수의 코인을 갖기 위해서는 단위가 큰 코인부터 채워야 한다. 따라서 coin을 내림차순 정렬해주고 하나씩 차례대로 계산을 해주면 된다.

K원을 현재 코인으로 나눈 값의 몫을 누적해서 개수로 추가해주고 나머지는 다음 계산을 위해 저장한다.

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

coin.sort(reverse=True)
count = 0
wallet = 0

for i in coin:
    count += k // i
    k = k % i

print(count)

 

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !