백준 11047. 동전 0 [Python]

• 문제 : 동전 0
• 난이도 : 실버 3
• 언어 : Python
• 문제 링크 : https://www.acmicpc.net/problem/11047

N, K = map(int, input().split())
coin = []
for _ in range(N):
    coin.append(int(input()))

cnt = 0
num = K
for i in range(N-1, -1, -1):
    if num == 0:
        break
    if num - coin[i] >= 0:
        cnt += (num // coin[i])
        num = num % coin[i]
print(cnt)

그리디 문제.

역순으로 동전을 빼나가면서 현재 값을 갱신하며 동전의 개수 또한 세줌.

자칫하면 시간초과가 날 수 있으므로 효율적인 코드가 중요한 것 같다.