11047번 : 동전0

문제보기

파이썬

import sys


n, k = map(int, sys.stdin.readline().split())
arr = []
count = 0

for i in range(n):
    arr.append(int(sys.stdin.readline()))


for i in range(len(arr)):
    mok = k // arr[len(arr)-1-i]
    count += mok
    k -= arr[len(arr)-1-i] * mok

print(count)

코드 설명

• 동전의 갯수, 목표 금액을 입력받고, arr 배열에 입력받은 값들을 집어넣음
• 제일 큰값(배열의 맨뒤)부터 역순으로 오면서 몫을 계속 더함
• 몫의 최종값이 최소 동전의 개수

포인트

자주 볼 수 있는 그리디의 기본인 동전 계산 문제!