11047번 : 동전 0 - Python

문제

https://www.acmicpc.net/problem/11047

풀이

가지고 있는 동전 중 가장 큰 동전부터 K에 얼마나 들어가는지 계산하는 방법으로 풀면 된다. 한번씩 빼는 방법 보다는 나누기와 나머지 연산을 이용해서 가장 큰 동전이 K에 들어갈 수 있는 방법을 계산하는게 빠르다.

코드

from sys import stdin

input = stdin.readline

N, K = map(int,input().split())
N_array = [int(input()) for _ in range(N)]
N_index = N-1
count = 0

while K!=0:
    if N_array[N_index] <= K:
        count += K // N_array[N_index] #K에 N_array[N_index]에 해당하는 돈을 얼마나 뺄 수 있는지 계산해서 더한다.
        K %= N_array[N_index] #K에 N_array[N_index]에 해당하는 돈을 얼마나 뺄 수 있는지 계산해서 뺀값을 K에 넣는다.
    else:
        N_index-=1

print(count)