[백준] [파이썬/Python] 11047번: 동전0 풀이 / 그리디알고리즘 설명 / sort()/내림차순 정렬

[백준] [파이썬/Python] 11047번: 동전0 풀이 / 그리디알고리즘 설명

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

 

00. 문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

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

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

출력

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

---

01. 풀이

-> 이 문제는 그리디 알고리즘으로 풀면 된다.

• 가지고 있는 동전 중 큰 단위가, 항상 작은 단위의 배수라면, 작은 단위의 동전을 종합해 다른 해가 나올 수 없기 때문에 그리디 알고리즘이 가능하다.
• → 따라서 가장 큰 동전단위 단위부터 시작하여 계산하면 필요한 동전 개수의 최솟값을 구할 수 있다.
• 동전의 종류가 N개일때, 시간 복잡도는 $O(N^2)$이다.
  • (동전의 종류만큼 진행하기 때문이다.)

 

Q. 그리디 알고리즘(탐욕법, 욕심쟁이 알고리즘)이란?

• 매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하는 알고리즘.
  • https://namu.wiki/w/그리디 알고리즘
• 이러한 방법을 이용해 최적의 해를 구할 수 있는지 검토한다.
• 그리디를 이용하여 최적의 해가 되는지 추론해서 적절히 사용해야 한다.

 

---

02. 코드

from sys import stdin

coin = []
count = 0

# --입력 --#
N, M = map(int,stdin.readline().split())

for i in range(N): #N개만큼 동전의 가치 입력
    coin.append(int(stdin.readline()))

coin.sort(reverse=True) # 내림차순 정렬

#-- 수행 --#
for value in coin:
    count = count + (M//value) # 필요한 코인수 count
    M = M % value # 쓰고 남은 돈 
    if(M <=0):
        break

print(count)

1. N,M을 stdin.readline()으로 입력받았다
2. coin이라는 리스트를 따로 만들어서, N개만큼 동전 가치를 입력받을때마다 append()함수로 추가시켜줬다
3. 그리디 알고리즘을 위해 가장 큰 단위부터 진행해야 하므로, coin 리스트를 내림차순 정렬해줬다.
   1. 리스트이름. sort(reverse=True) : 내림차순 정렬
   2. 리스트이름.sort() : 오름차순 정렬
4. coin리스트의 요소를 차례대로 돌면서, count에 각 요소(단위)당 필요한 코인 수를 //(몫을 구해줌)를 이용하여 구한 뒤 추가해줬다.
5. M에는 요소당 사용한 코인을 쓰고 남은 돈을 계산해줬다.
6. M의 값이 먼저 0보다 작아진 경우, 반복문을 탈출하도록 했다. (break)

---

03. 결과

 

---

04. 후기

그리디 알고리즘은 쓸 수 있는지 없는지 판단하는게 정말 중요한 것 같다.

 

 

풀이 출처 참고 :

• 참고: https://namu.wiki/w/그리디 알고리즘
• 참고: https://www.youtube.com/watch?v=2zjoKjt97vQ