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

동전 0

---

풀이과정

1. 준규가 가지고 있는 동전의 종류를 coins 리스트에 입력 받는다.
2. 단위가 큰 동전부터 최대한 많이 사용해야하므로, coins 리스트를 뒤집어 for문을 돌리며 동전 단위가 K보다 작거나 같으면 최대한 많은 개수를 사용한다.
3. for문을 돌리다가 동전의 가치의 합이 K가 되면 break를 걸어 빠져나온다.

단위들이 앞뒤로 배수 관계일 때는 이렇게 큰 단위부터 최대한 할당하는 방식(Greedy)으로 동전 개수의 최솟값을 구할 수 있다. (문제의 조건 중 '1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수'라는 부분)

Python Code

import sys

temp = sys.stdin.readline().rstrip().split()
N = int(temp[0])
K = int(temp[1])

coins = []
answer = 0
for i in range(N):
    coins.append(int(sys.stdin.readline().rstrip()))

for i in reversed(coins):
    if i <= K:
        answer += K//i
        K -= K//i * i
    if K == 0:
        break

print(answer)

오류와 해결

처음에 동전 종류당 사용할 개수를 구하는 for문 안에 while문을 사용했더니 시간초과가 발생했다.

for i in reversed(coins):
    while i <= K:
        answer += 1
        K -= i
    if K == 0:
        break

이렇게 하면 답은 맞지만 시간초과가 발생한다. while문을 사용하지 않고 if문과 버림 나눗셈(//)을 사용하여 동전 종류당 사용할 개수를 구했더니 해결되었다.

새로 알게 된 부분

• 리스트 뒤집기

lst.reverse()

reverse() 함수는 리스트의 순서를 거꾸로 뒤집는다.

l2 = reversed(l1)

reversed() 함수는 인자로 들어간 리스트를 거꾸로 뒤집은 새로운 리스트를 리턴한다.

• 버림 나눗셈(//)
  버림 나눗셈(//)을 사용하면 나눗셈한 결과에서 소수점 이하를 버린 값이 나온다.
  ex) 4200//1000 = 4
  a//b는 int(a/b)와 결과가 같지만 a//b가 시간적인 면에서 더 효율적인 것 같다.