[백준] 11047번 동전 0

💡문제접근1

• 처음에는 동전의 가치를 내림차순으로 정렬해서 반복문을 돌려 K보다 작거나 같은 최초의 값이 나타나면 K에서 동전의 가치를 빼주고 동전개수를 하나 증가시키고 인덱싱을 다시 처음으로 바꿔 탐색하는 방법을 택했다. 하지만 이 방법은 시간초과가 발생했다.

💡코드1

import sys

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

coin.sort(reverse=True)
cnt = 0
money = 0
while True:
    if K == 0:
        break
    if coin[money] <= K:
        K -= coin[money]
        money = 0
        cnt += 1
    else:
        money += 1
print(cnt)

💡문제접근2

동전의 가치를 내림차순으로 정렬하고 K보다 작거나 같은 최초의 값이 나타나면 K와 나눴을 때 나오는 몫을 더해주고 K에서 그만큼의 값을 빼주는 과정을 반복하면 [문제접근1]과 시간을 비교했을 때 확연히 다르다는 것을 알 수 있었다.

💡코드2(메모리 : 30616KB, 시간 : 36ms)

import sys

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

coin.sort(reverse=True)
cnt = 0
while True:
    if K == 0:
        break
    else:
        for money in coin:
            if money <= K:
                cnt += (K // money)
                K -= (K // money) * money
print(cnt)

💡소요시간 : 7m