[BOJ 11047] 동전0 (Python)

kimdukbae·2021년 4월 7일
0

문제

링크



풀이

굉장히 쉽다고 느꼈던 문제였다. 개인적으로 실버2 난이도가 아니였다고 생각한다...

동전 중 가장 큰 금액의 동전부터 탐색하도록 하였다. 왜냐하면 K원을 만드는데 필요한 동전 개수의 최솟값을 구해야하기 때문이다. 동전이 K원보다 크면 해당 동전으로 K원을 만들 수 없기 때문에 다음 동전으로 넘어갔고, 나눗셈과 나머지 연산을 통해 답을 구했다.



코드

import sys

input = sys.stdin.readline
N, K = map(int, input().split())
coin = []
ans = 0

for i in range(N):
    coin.append(int(input().rstrip()))

for i in range(N - 1, -1, -1):
    if coin[i] > K:
        continue
    ans += K // coin[i]
    K %= coin[i]

print(ans)
profile
A Student of Computer Science

0개의 댓글