BOJ_11047 : 동전 0

👉 문제링크

11047번: 동전 0

---

---

🔸 문제 분석 🔸

• 동전 종류 수 n과 만들 가치의 합 k, 동전 종류를 입력받는다.
• 동전을 최소로 사용하면서 k를 만든다.

🔸 코드 🔸

import sys

n, k = map(int, sys.stdin.readline().split())
coin = []

for i in range(n):
    c = int(sys.stdin.readline())
    if c <= k:
        coin.append(c)

answer = 0

for i in coin[::-1]:
    if k >= i:
        answer += k//i
        k %= i
sys.stdout.write(str(answer) + "\n")

🔸 코드 해석 🔸

• k의 범위가 1억까지 가므로 빠른 입출력을 사용했다.
• 가치의 합을 만드는데 가치보다 작은 동전만 쓰이므로, k보다 작은 동전 종류만 coin 리스트에 저장한다.
• 리스트를 역으로 순회하며 동전의 개수를 센다.
  • 남은 가치의 합이 현재 동전보다 크거나 같아야 한다.
  • 현재 동전 종류 i 로 최대한 k를 채워야 한다.

---

🔸 end 🔸

• 그리디 알고리즘의 기초 문제인 것 같다. 생각보다 쉽게 풀은 것 같다.