<백준 문제풀이: 11047번> 파이썬 - 동전 0

가장 큰 지폐 단위부터 차례대로 계산하면 되는 그리디 알고리즘인 듯 했다. 따라서 다음과 같이 풀었다:

시간 초과 뜬 풀이

import sys

N, K = map(int, sys.stdin.readline().split())
values = []
for i in range(N):
    value = int(sys.stdin.readline())
    if value < K:
        values.append(value)
values.sort(reverse=True)
count = 0
for j in values:
    while True:
        if K >= j:
            K -= j
            count += 1
        else:
            break
print(count)

파이썬 IDLE 에서 확인해보니 정답은 맞다. 하지만 while문을 실행하는 것이라 시간 초과가 뜰 수 밖에 없는 듯 하다. 따라서 다음과 같이 간단하게 바꿔서 풀었다.

제출한 정답

import sys

N, K = map(int, sys.stdin.readline().split())
values = []
for i in range(N):
    value = int(sys.stdin.readline())
    if value <= K:
        values.append(value)
values.sort(reverse=True)
count = 0
for j in values:
    if K >= j:
        num = K//j
        K -= j*num
        count += num
    else:
        continue
print(count)

단순히 for문 한개를 사용하여 풀었는데, 이는 각 지폐 단위에 대하여 K에 대해 몫을 구하는 방식을 사용하여 while문으로 처리할 것을 한방에 처리하면서 시간을 단축 할 수 있었다.