백준 11047 풀이 (동전 0, 그리디)

간단한 그리디 문제이다. k값을 만족시키기 위해 동전이 몇개 필요한지 구하는 문제이다.

처음에는 해당 동전이 k보다 작은경우 뺄셈을 해서 구하게 만들었는데

70%까지 가더니 시간초과로 틀려버렸다. 

생각해보니 굳이 빼지 않고 나누면 훨씬 더 빨리 구할 수 있었다. 그래서 코드를 살짝 수정하여 제출했다.

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

coin =[]
for _ in range(n):
    coin.append(int(input()))
print(coin)

number = 0
for ci in range(n-1,-1,-1):
    while 1:
        if coin[ci] <= k:
            number += (k//coin[ci])
            k %= coin[ci]
            continue
        else:
            break
    if k == 0:
        break
print(number)