[백준 알고리즘] 백준 11047번: 동전 0 / 파이썬 Python3 (그리디)

🔔 문제

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

---

🔐 해결 (소스 코드)

# 첫째 줄에 N과 K가 주어진다.
n, k = map(int, input().split())

count = 0

coin_type = []
# n개의 줄에 동전의 가치가 오름차순으로 주어진 것을 리스트에 넣는다.
for _ in range(n):
    coin_type.append(int(input()))

coin_type.sort(reverse=True)
# 동전 개수의 최솟값을 출력하려면 동전의 가치가 큰 순서대로 계산해야하므로 내림차순으로 정렬해줌    

# k원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.
for coin in coin_type:
    count += k // coin
    k %= coin

print(count)

---

📝 후기

먼저 풀었던 백준 5585번 거스름돈 문제를 풀었던 코드를 기반으로 응용하여 해결할 수 있었다.

다소 쉬웠던 문제이니 만큼 이후에는 그리디 알고리즘에서 좀 더 난이도 있는 문제들을 풀어서 풀이를 올렸으면 좋겠다!

---

👣 참고하기

ⓐ 그리디 알고리즘 강의 정리노트 보기

ⓑ 백준 5585번: 거스름돈 문제 풀이 보기

맨 위로 이동하기