import sys
input = sys.stdin.readline
N, K = map(int, input().split())
coins = []
count = 0
coins = [int(input()) for _ in range(N)]
coins.sort(reverse=True)
for coin in coins:
count += K // coin
K = K % coin
if K == 0: break
print(count)
동전이 오름차순으로 입력되는데 우리는 필요한 동전 개수의 최솟값을 출력해야하기 때문에 내림차순 정렬을 한다.
1. K원을 큰 동전부터 나눈 후 몫을 count 한다.
ex) 4200원이면 4200 // 1000 > 동전 4개 카운트
2. K원을 큰 동전으로 나눈 나머지를 다시 반복해서 나눌 수 있도록 K에 넣는다.
ex) 4200 % 1000 > 200원
남은 200원으로 반복문 수행, 남은 돈이 0이 될 때까지 반복
'코테 > 백준' 카테고리의 다른 글
백준 10816 숫자 카드 2 - 파이썬 (0) | 2024.06.25 |
---|---|
백준 1920 수 찾기 - 파이썬 (0) | 2024.06.25 |
백준 11399번 ATM - 파이썬 (0) | 2024.06.25 |
백준 1931 회의실 배정 : 파이썬 (0) | 2024.06.25 |
1157번: 단어공부 - 파이썬 (0) | 2024.05.14 |