[파이썬] 백준 11047 : 동전 0

[파이썬] 백준 11047 : 동전 0

https://www.acmicpc.net/problem/11047

11047번: 동전 0

실버 3

그리디 알고리즘

---

접근

실버 3이라 하기에는 쉬운 문제였다.

아무래도 그리디 알고리즘 문제가 전반적으로 구현 난이도가 쉬운 편이라서 그런 듯.

 

반복문을 거꾸로 돌리는 방법으로 동전의 단위를 큰 순서대로 순회할 수 있다.

해당 동전이 만들려는 K원보다 클경우는 다음 동전 단위로 차례를 넘기고, 몫과 나머지를 적절히 이용하여 K가 0이 될 때 반복문을 빠져나오도록 한다.

 

코드 풀이

import sys
N, K = map(int, sys.stdin.readline().split())
lst = [int(sys.stdin.readline()) for _ in range(N)]
cnt = 0
for i in range(N)[::-1]:
    if lst[i] > K:
        continue
    cnt += K // lst[i]
    K %= lst[i]
    if K == 0:
        break
print(cnt)

 

[::-1]로 반복문을 거꾸로 돌릴 수 있다.

내림차순 해서 반복문 하는 것보다 훨씬 간결하다.

K = 4200일 때, 50000 ~ 5000까지의 단위는 K를 만들 수 없으므로 continue로 넘기고,

K보다 작은 단위라면 K에 그 단위를 나눈 몫을 동전 개수 cnt에 더해준다.

그 나머지는 K에 다시 대입하면 K가 0이 될 때 반복문을 탈출할 수 있도록 만들 수 있다.

 

4200원에서 시작해서 정확히 0원이 되면 반복문을 탈출하는 방법이다.