[DP] 아이템을 적절히 고르는 문제 / 동전 거슬러주기

문제링크

https://www.codetree.ai/missions/2/problems/coin-change?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

1. 핵심

• 동전 거슬러주기 유형 중 같은 동전을 중복해서 줄 수 있는 유형
• Top-down의 핵심은 점화식이며 내가 설정한 숫자들의 의미를 잘 부여야한다.
  • ret = inf
  • dpf(money) = min(ret, dpf(money - coin) + 1) where coin <= money and coin in coins
  • dp는 -1로 초기화된 상태이며, ret은 inf로 초기화되어있다. 
    • -1 의 의미: not-visted 방문하지 않은 금액
    • inf 의 의미: 만들 수 없는 금액
    • 0의 의미: 0원을 의미한다. 0원은 inf와 -1과는 의미가 다르다. 예를 들어 2원을 만들어야하는데 2원만 가지고 있다고 해보자. 그렇다면 경우의 수는 1이 된다. 이를 점화식에서 나타내보면 dpf(2원) = min(ret, dpf(2- 2) + 1) = min(ret, dpf(0) + 1) 로 dpf(0) = 0 이어야 한다. 따라서 money = 0일 때는 dpf(0) = 0이 되도록 한다.
• 동전 거슬러주는 문제에서 dpf(0) = 0이 되도록 초기화하는게 기본이다.

2. 코드(Python)

import sys
sys.setrecursionlimit(10 ** 5)

n, m = map(int, input().split())
# 동전 중복 선택 가능
# 동전 거슬러 주기 - dp
coins = list(map(int, input().split()))
inf = int(1e9)
dp = [-1 for _ in range(m + 1)]

# dpf(금액x) = max(ret, dpf(x - coin) + 1) where coin in coins and coin <= x
# inf: not-visited
# 0: impossible
# so, dp[0] = 0? impossible?
# dp[2] -> dp[0] -> dp[0]은 impossible이 아니다.

# -1: not-visited
# inf: impossible

def dpf(money):
    if money == 0:
        return 0

    if dp[money] != -1:
        return dp[money]
        
    # 1원으로만 전부 나눠줄 경우 최대가 된다.
    # 최소 동전보다 작은 m은 돈을 거슬러 줄 수 없다.
    # 1종류 1원
    # 2원(으로 거스릴 수는 없음)
    ret = inf
    for coin in coins:
        if coin <= money:
            ret = min(ret, dpf(money - coin) + 1)

    # 0의 의미: 동전으로 만들 수 없다.
    # 오해하면 안되는게 money = 0이면 당연히 만들 수 없지만 0이 아니라 무조건 만들 수 있는 것도 아니다.
    # 나에게 있는 동전이 1000원 1개 밖에 없다고 가정했을 때 10원을 어떻게 나누어주는가?
    # 따라서 주어진 코인들보다 money가 커야한다.
    dp[money] = ret

    return ret

k = dpf(m)
if k == inf:
    print(-1)
else:
    print(k)