[백준] 11047번 (python 파이썬)

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

그리디 문제의 기초이다.

최소의 동전개수로 해당 가격을 만드는 문제

 

주어진 제일큰 동전부터 시작하여 만들려고 하는 가격을 나눴을때 몫이 있다면 동전의 개수를 해당 몫만큼 더해주고 나머지를 가지고 다음 계산을 이어간다.

( 가장 큰 동전부터 선택하여 구하는 것 ) 

 

n, k = map(int, input().split())
a = list()

for _ in range(n):
    a.append(int(input()))

result = 0

def coin_zero():
    global k, a, result
    for i in range(n-1, -1, -1):
        quotient = k // a[i]
        remainder = k % a[i]
        if quotient > 0:
            result += quotient
            k = remainder
    return result

print(coin_zero())

 

for문에 나머지가 0일때 break을 걸어서 반복문을 빠져나오도록 했었는데 이 조건문을 거는게 시간에서 더 느리게 나왔다. 왜지??