알고리즘 - Python / 백준 - 11047번 : 동전 0

11047번: 동전 0 (acmicpc.net)

11047번: 동전 0

 

---

풀이

• 문제를 읽어보고 동전의 합을 표현할 수 있는 가장 큰 단위부터 표현하면 풀 수 있다는 것을 발견했다.
• 이후 문제의 범위를 보니 최대 10개를 확인하는 범위가 크지 않은 그리디 알고리즘 문제이다.
• 모든 범위를 돌면서 넣을 수 있는 만큼의 동전을 그리디 알고리즘 방식으로 넣고 넣은 횟수를 더해 출력하면 된다.

 

import sys

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

for i in range(0,n):
  ip = int(sys.stdin.readline())
  stack.append(ip)

ans = 0

for t in range(n-1,-1,-1):
  if stack[t] <= k:
    ans += k // stack[t]
    k = k % stack[t]
print(ans)

---