[백준] 11047번(동전 0) with Python

문제

www.acmicpc.net/problem/11047

11047번: 동전 0

 

풀이

동전의 갯수가 최솟값을 가져야 하기 때문에 큰 수 부터 나눠준다. 동전의 가치가 오름차순으로 입력이 되기 때문에 coin[::-1](리스트 역으로 출력) 사용, pop() 으로 작성해도 된다. 

1. k원을 동전의 가치로 나눠주고(몫만 필요하기 때문에 // 사용)

2. k원에서 (1에서 나온 몫 * 동전의 가치)를 빼준 후

3. 코인 개수를 1에서 나온 몫 만큼 증가

위 작업을 k가 0원이 될 때 까지 반복한다.

답

import sys

input = sys.stdin.readline

n, k = map(int, input().split())
coin  = []
coin_cnt = 0

for i in range(n) :
  coin.append(int(input()))

while k > 0 :
  for c in coin[::-1] :
    cnt = k // c
    k -= cnt * c
    coin_cnt += cnt

print(coin_cnt)

# 다른 풀이

n, k = map(int, input().split())
coin  = []
coin_cnt = 0

for i in range(n) :
  coin.append(int(input()))

while k > 0 :
  c = coin.pop()
  coin_cnt += k // c
  k %= c