[백준/알고리즘/python/java] 11047번 - 동전 0

이미지를 누르면 문제링크를 보실 수 있습니다.

이미지를 누르면 문제링크를 보실 수 있습니다.

[11047번 - 동전 0]

 

전형적인 그리디 알고리즘 문제이다.

주어진 금액을 만드는데 필요한 동전개수의 최소값을 구하는 것이므로,

주어진 금액에서 큰 금액을 빼가면서 개수를 구하면 최소 개수를 구할 수 있을 것이다.

 

(맨 처음 풀었던 코드-시간초과)

n, k = map(int, input().split())
coins = []
count = 0
for i in range(n):
    coins.append(int(input()))
coins.reverse()
standard = coins[0]
for coin in coins:
    standard = coin
    if(k-standard < 0):
        continue
    else:
        while(k-standard >= 0):
            k -= standard
            count += 1
print(count)

동전 리스트를 적은 금액 순서로 입력받으므로, reverse() 를 통해 리스트를 내림차순으로 바꿔주었다. 

또한, 동전 리스트에 있는 금액을 돌 때, 금액을 한번씩 빼면서 반복문을 돌았는데, 시간초과가 났었다.

바로 몫으로 나누는 코드로 바꿨더니 시간초과 문제에서 벗어날 수 있었다.

 

(아래 최종 코드-python)

n, k = map(int, input().split())
coins = []
count = 0
for i in range(n):
    coins.append(int(input()))
coins.reverse()
standard = coins[0]
for coin in coins:
    standard = coin
    if(k-standard < 0):
        continue
    else:
        while(k-standard >= 0):
            mok = k // standard
            k -= standard*mok
            count += mok
print(count)

while문을 돌면서 개수를 파악할 때, 기준값을 한번씩 빼면서 굳이 while문을 처음부터 안돌고,
k 값에서 기준값을 나눈 몫만큼 동전개수에 더해주고, while문을 빠져나오면 불필요한 계산을 줄일 수 있었다.