11047번 : 동전 0

문제보기

파이썬

# n : 동전 종류, k : 목표 금액
n, k = map(int, input().split())

coins = []
cnt = 0

for i in range(n):
    coins.append(int(input()))

coins.sort(reverse=True)

for i in coins:
    mok = k // i
    cnt += mok
    k -= mok * i

    if k == 0:
        break

print(cnt)

풀이

• 기본적인 그리디 문제
• 오름차순으로 입력받앗기에 내림차순으로 정렬한뒤 계산