[Python] 백준 11047번 : 동전 0 (S1) - 그리디단계별1

#문제

www.acmicpc.net/problem/11047

11047번: 동전 0

#풀이 & 학습한 내용

"동전의 조건이 특별해서 동적 프로그래밍보다 빠르게 답을 찾을 수 있는 문제"입니다. 큰 단위가 항상 작은 단위의 배수이므로 가장 큰 단위의 동전부터 차례대로 빼주면 됩니다. 만약 이러한 특별한 동전의 조건이 없다면 다이나믹 프로그래밍을 통해 문제를 풀어야 할 것입니다.

 

#소스코드

coins=[] #동전의 종류저장
coin_num=0 #필요한 최소동전갯수
 
N,K=map(int,input().split())
#print(N,K)
 
for i in range(N):
  coin = int(input())
  coins.append(coin)
 
#print(coins)
 
while K!=0:
  pop_coin = coins.pop()
  coin_num += K//pop_coin
  K= K%pop_coin
 
print(coin_num)

 

github.com/HoYoungChun/Algorithm_PS/blob/master/Greedy/BOJ_11047.py

HoYoungChun/Algorithm_PS