[코테/백준] Python 동전 0 - 11047번

성공 | 시도 2번

 

🔗 [백준] 11047번 동전

🔗 11047 : [그리디 알고리즘] 동전 0(py)

---

문제 설명

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

---

문제 분석

- 동전 단위를 내림차순으로 정렬해서 금액을 큰 단위에서 작은 단위로 나눌 수 있게 해야 한다. 

---

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 A_i가 오름차순으로 주어진다. (1 ≤ A_i ≤ 1,000,000, A₁ = 1, i ≥ 2인 경우에 A_i는 A_i-1의 배수)

---

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

---

입력과 출력 예시

입력	출력
10 4200 1 5 10 50 100 500 1000 5000 10000 50000	6
10 4790 1 5 10 50 100 500 1000 5000 10000 50000	12

---

내 소스

n, k = map(int, input().split())

money_units = [] 
for _ in range(n):
    money_units.append(int(input()))

money_units.sort(reverse=True)

cnt = 0
for money_unit in money_units:
    if money_unit <= k:
        cnt += k // money_unit
        k = k % money_unit
print(cnt)

 

소스 설명

n, k = map(int, input().split())

money_units = [] 
for _ in range(n):
    money_units.append(int(input()))

[1 - 5] : 동전 종류와 동전 합을 n, k 변수에 담는다. 동전 종류만큼 동전 단위를 입력받아 리스트에 추가한다.

 

money_units.sort(reverse=True)

[7] : 동전 단위를 내림차순으로 정렬한다.

 

cnt = 0
for money_unit in money_units:
    if money_unit <= k:
        cnt += k // money_unit
        k = k % money_unit

[9 - 13] : 금액이 동전 단위보다 크거나 같다면 cnt에는 금액(k)을 동전 단위로 나눈 몫을 저장하고 금액은 금액을 동전 단위(k)로 나눈 나머지를 저장한다. 

---

다른 코드 분석

- 어떤 분 [1], [3]은 금액(k)가 0보다 작거나 같을 때 break할 수 있게 코딩하였다.

- [2] 동전 0 문제가 특이한 조건에 의해 그리디 알고리즘을 적용할 수 있다는 것을 알았다.

 A₁ = 1, i ≥ 2인 경우에 A_i는 A_i-1의 배수

→ 큰 동전이 전부 작은 동전의 배수가 된다는 뜻이라고 한다. 

---

Ref. 

1. 문제 풀이 / https://puleugo.tistory.com/20

2. 문제 풀이 / https://god-gil.tistory.com/64

3. 문제 풀이 / https://velog.io/@yoonkeem/BOJ-11047%EB%B2%88-%EB%8F%99%EC%A0%84-0-%ED%8C%8C%EC%9D%B4%EC%8D%AC

---

* 잘못된 부분에 대해 댓글 남겨주시면 감사하겠습니다! 😀