백준 11047번 "동전 0"

문제

백준 11047번 동전 0

풀이

K보다 작은 Ai의 최대값을 K를 나누어 그 몫을 count에 추가하고, K에 다시 나머지를 저장한다.
K의 값이 0이 될 때까지 반복하면 된다.

Python 코드

import sys

input = sys.stdin.readline

n, k = map(int, input().split())
arr = []

for _ in range(n):
  arr.append(int(input()))

count = 0
arr.sort(reverse=True)

for i in range(n):
  if k==0:
    break
  elif arr[i]>k:
    continue
  else:
    count += k//arr[i]
    k %= arr[i]

print(count)