11047: 동전 0 - Python

문제

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

풀이 1

import sys
input = sys.stdin.readline

N, amount = map(int, input().split())
coins = [int(input()) for _ in range(N)]
coins = coins[::-1]

total_cnt = 0
for coin in coins:
    if amount > 0 and amount >= coin:
        cnt = amount // coin
        amount -= coin * cnt
        total_cnt += cnt

print(total_cnt)

• 전형적인 그리디 알고리즘 문제다.
• if 조건을 주지 않아도 될 것 같다는 생각이 든다.

풀이 2

import sys
input = sys.stdin.readline

N, amount = map(int, input().split())
coins = [int(input()) for _ in range(N)]
cnt = 0

for coin in coins[::-1]:
    cnt += amount // coin
    amount %= coin

print(cnt)

• 풀이 1을 훨씬 간단히 구현할 수 있다. 역시 조건은 필요 없었다.

---

오늘의 교훈

• 전형적인 그리디 문제에 적용할 수 있는 코드를 익혀두자.

amount = 2000
cnt = 0

coins = [500, 100, 50, 10] # 내림차순 정렬돼있어야 함.

for coin in coins:
    cnt += amount // coin
    amount %= coin

print(cnt)

참고 자료

• [알고리즘] 그리디(Greedy) 알고리즘과 예제 (파이썬)
  
• (이코테 2021 강의 몰아보기) 2. 그리디 & 구현