[알고리즘] 그리디(Greedy) 백준 11047번 - 동전0

1차 코드

N, K = map(int, input().split(' '))
coin = [int(input()) for _ in range(N)]
coin.sort(reverse=True)

count = 0   # 동전 개수 최솟값
coin_sum = 0  # K값을 만들기 위한 돈
for i in range(len(coin)):
  if coin[i] < K:
    while coin_sum < K:
      if coin_sum + coin[i] > K:
        break
      else:
        coin_sum += coin[i]
        count += 1
    
  if coin_sum == K:
    break

print(count)

예를 들어, 4200원 이라면 1000원을 4번 더하고, 100원을 2번 더하는 방식으로 문제를 풀었다. 하지만 결과는 시간초과!!!
낮은 가격은 문제 없지만, 높은 가격의 경우 더해야할 횟수가 많아서 그런 것 같다. While을 쓸 때 주의하자.

2차 코드

N, K = map(int, input().split(' '))
coin = [int(input()) for _ in range(N)]
coin.sort(reverse=True)

count = 0   # 동전 개수 최솟값
for i in range(len(coin)):
  if K >= coin[i]:
    num = K // coin[i]
    K -= coin[i] * num
    count += num
  if K == 0:
    break

print(count)

풀이과정

1. 입력 받은 동전들을 reverse 순으로 정렬한다.
2. 나눗셈을 활용하는데, 몫은 동전 개수가 되고 나머지는 다음에 필요한 동전을 의미한다.
3. 입력받은 돈 K 가 0원이 되면 반복문을 빠져나온다.