[Python] 백준 11047번

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

N, K = map(int, input().split())
coins = []
answer = 0

for i in range(N):
    value = int(input())
    coins.append(value)

for value in coins[::-1]:
    n, K = divmod(K, value)
    answer += n

print(answer)

• 동전문제를 그리디 방식으로 풀이하는 것은 전에 파이썬 알고리즘 리뷰 책으로 공부를 했을 때에도 해본 것이라 어려운 문제는 아니었다. 다시 한번 그 책의 내용을 생각해보면 동전의 액수가 서로 배수 관계일 때만 그리디 방식으로 이 문제를 풀 수 있다. 동전의 액수가 배수 관계가 아닌 동전이 하나라도 있을 경우 그리디 방식으로 풀 수 없다.
• 구현은 어렵지 않았지만 뒷부분에서 약간 실수가 있어 첫 제출은 시간 초과가 났다. 그 코드는 동전의 갯수를 세는 방식을 반복문을 사용했는데 시간초과가 나서 그 다음 제출한 코드는 위처럼 divmod를 사용하여 나눗셈의 몫과 나머지를 이용했다.

시간초과가 난 풀이

N, K = map(int, input().split())
coins = []
answer = 0

for i in range(N):
    value = int(input())
    coins.append(value)

for value in coins[::-1]:
    while K >= value:
        K -= value
        answer += 1

print(answer)