[Baekjoon]백준 11047 동전 0(실버 4) - Python

문제설명

예제

문제를 살펴보면 최소한의 동전을 사용하여 비용을 지불하여야한다

최소한의 동전을 사용하려면 가진 동전중에서 남은 비용에 가장 가까운 동전을 사용하여야한다

즉 5000원이 남았을때 500, 1000, 5000, 10000이 있다면 5000원을 사용하는 것이 제일 효율적이다

이러한 계산을 하기 위해 일단 입력받은 동전을 리스트로 저장해주었다

제일 뒤에 위치한 index가 가장 큰 금액이므로 index의 시작점을 n-1로 두어 -1을 해가면서 확인하면 된다

그리고 해당 동전이 지불해야하는 금액보다 작다면 해당 동전의 값을 빼며 while문을 통해 반복해준다

kind, money = map(int, input().split())
coin = []

for _ in range(kind):
    coin.append(int(input()))
    
cnt = 0
index = kind - 1
while money > 0:
    if coin[index] <= money:
        money -= coin[index]
        cnt += 1
    else:
        index -= 1
        
print(cnt)

제출하였더니 시간초과가 발생하였다

음...?이라고 생각해보다 큰 실수를 한 것을 알 수 있었다 빼기가 아니라 나눗셈을 하는 것이 훨씬 빠르기 때문이다

나눈 후 몫은 cnt변수의 값으로, 나머지는 money에 저장하여 0원이 될때까지 반복하면 된다

kind, money = map(int, input().split())
coin = []

for _ in range(kind):
    coin.append(int(input()))
    
cnt = 0
index = kind - 1
while money > 0:
    if coin[index] <= money:
        cnt += money // coin[index]
        money %= coin[index]
    else:
        index -= 1
        
print(cnt)

해당 코드는 이전의 코드보다 불필요한 계산이 적기 때문에 시간을 절약할 수 있다