백준 11047 - 동전 0 (Python)

백준 11047 동전

11047번: 동전 0

예제 풀이

10 4200
1
5
10
50
100
500
1000
5000
10000
50000

10가지의 동전을 4200원의 최소 동전 개수를 구하려면
큰 숫자부터 값을 빼줘야 한다

4200 - 1000 = 3200
3200 - 1000 = 2200
2200 - 1000 = 1200
1200 - 200 = 200
200 - 100 = 100
100 - 100 = 0
총 6번

1. 동전을 내림차순으로 우선 정리 -> 큰값부터 빼줘야 하기 때문
[ 50000, 10000, 5000, 1000, 500, 100, 50, 10, 5, 1 ]

2. 4200원보다 작고 나누어지는 값 중에 가장 큰 수를 골라 우선 나눈다
    4200 / 1000 = 4
    1000동전이 4개 필요
    4200 = 4200 - 1000 * 4
    4200에서 동전 값만큼 빼준다   
    
3. 200보다 작고 나눌 수 있는 값중에 큰 수를 고른다
    200 / 100 = 2
    100동전이 2개 필요
    200 = 200 - 100 * 2
    
4. 해당 배열을 반복하면서 계산하면 완료

n,k = map(int, input().split())
coin_list = [int(input()) for i in range(n)] #n값 만큼 input
coin_list.sort(reverse=True) #내림차순 정리

count = 0 

for i in coin_list: # 동전리스트 만큼 순회
    q = k // i #큰 값부터 나눌수 있으면 나눠줌 
    k -= i * q
    count += q
    
print(count)