백준 11047번 동전 0 파이썬 풀이

Python

[Python] 백준 알고리즘 온라인 저지 11047 동전 0

11047 동전 0

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

11047번: 동전 0

필요한 동전의 최솟값은 k보다 작은 가장 큰 화폐들을 사용하고 잔돈을 사용하면 최솟값을 구할 수 있다. 이 개념만 안다면 어렵지 않게 문제를 풀이할 수 있다. 

---

코드

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]
cnt = 0
index = n - 1 # coins에서 가장 큰 단위부터

while k > 0:
    if coins[index] > k: # k 보다 coin[index]값이 크다면 인덱스 하나씩 내려감
        index -= 1
    else:
        cnt += k//coins[index]
        k %= coins[index]
print(cnt)

---

풀이

그리디 알고리즘 문제답게 다양한 화폐 단위를 제시하고 모든 화폐를 거쳐 k보다 작지만 단위는 가장 큰 동전을 찾고 k를 나눈 값을 cnt에 따로 추가한다.

남은 나머지 돈은 while문을 통해 k가 0원이 될 때까지 loop을 돌며 이전에 했던 방식을 그대로 사용하여 계산한다.

---

풀이 결과

11047 풀이 결과