문제 풀이

[11047번] 동전 0

• (핵심)가지고 있는 동전의 종류로 무조건 원하는 가치의 합을 만들 수 있습니다.
• 동전의 종류를 내림차순으로 정렬하고 차례대로 나눠 몫과 나머지를 계산한 뒤 몫은 모두 더하고, 나머지를 그 다음 크기의 동전 종류로 나눠 몫과 나머지를 계산하는 작업을 끝까지 반복하면 됩니다.

코드 풀이

import sys
N, K = map(int, sys.stdin.readline().split())

A = []
cnt = 0
for _ in range(N):
    x = int(sys.stdin.readline())
    A.append(x)

for i in range(N-1, -1, -1):
    cnt += (K // A[i])
    K %= A[i]

print(cnt)