[Python] BOJ/백준 11047번 동전 0

[문제]

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

11047번: 동전 0

 

[풀이]

문제 조건이 큰 동전은 모두 작은 동전의 배수이기 때문에 이 문제는 그리디 알고리즘으로 풀 수 있다.

만약 800원의 가치를 만들어야 하는데, 500원 400원 100원으로 주어지는 경우는 그리디 알고리즘을 쓰면 안된다. 

 

동전 문제에 그리디 알고리즘을 적용하는 것은 쉽다. 동전의 액면가만 보고 판단하면 되기 때문에

가장 큰 동전부터 시작해서 몫을 더해준 후 나머지 동전으로 앞 연산을 반복한다.

---

가장 큰 동전부터 시작해서 내림차순으로 비교하기 위해 동전의 가치를 담은 coin 리스트를 reverse 함수를 이용해 내림차순으로 뒤집어주었다.

 

만약 가치의 합인 k를 동전으로 나눴을 때 몫이 0이라면 가치가 더 작은 액수인 것이다. 따라서 더 작은 동전을 사용해야 한다. 동전으로 나눈 몫이 0보다 크다면, res에 몫을 저장하고, k는 나머지 값으로 초기화해준다.

 

위의 과정을 while문으로 반복하다가 k가 0이 되면 break문을 통해 탈출한다. 

 

 

[코드]

import sys

if __name__ == '__main__':
    n, k = map(int, sys.stdin.readline().split())
    coin = [int(sys.stdin.readline()) for _ in range(n)]
    coin.reverse()

    res = 0
    while True:
        for i in coin:
            if k // i > 0:
                res += k // i
                k = k % i
        if k == 0:
            break
    print(res)