[그리디] 백준 #11047 동전 0 - Python

🗂️ 문제

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

11047번: 동전 0

 

💡 접근법

그리디 알고리즘을 이용하여 문제에 접근한다.

즉 현재 시점에서 최선의 선택을 하고 이 선택이 전체 문제를 해결할 수 있는지 확인한다.

 

문제에서 제시한 대로 최소 동전 개수를 구하기 위해서는 가장 가격이 큰 동전부터 차례대로 순회하면 된다.

 

😎 내 코드

import sys

N, K = map(int, sys.stdin.readline().split())
A = [int(sys.stdin.readline().rstrip()) for _ in range(N)]

cnt = 0
for a in reversed(A):
    cnt += K // a
    K %= a  

print(cnt)

 

✅ 정답 확인