🏃[알고리즘/python] DP - 동전 유형 접근 컨셉

동전 유형

1. 무한개의 동전 가짓수를 가지고 목표 금액을 만들기 위해 필요한 최소 동전 수 #무한개 # 최소 아이템수 #조합

2. 유한개의 동전 가짓수를 가지고 목표 금액을 만들 수 있는 가짓 수 #유한개 # 가짓수 #조합

3. 무한개의 동전 가짓수를 가지고 목표 금액을 만들 수 있는 가짓 수 #무한개 #가짓수 #조합

TODO: 배낭문제를 동전유형으로 풀어보기

# 무한개 #최소 아이템수 #조합

백준 #2294 동전2

Q. 백준 #11047 동전0 은 Greedy 알고리즘으로 풀던데 차이점이 뭔가요?
A. [동전0]은 요소가 서로 배수 관계이기에 동전을 내림차순해서 greedy 선택을 할 수 있는 조건이 주어집니다.
이와 달리 [동전2]는 서로 배수 관계가 아니이기에 모든 경우의 수를 구해야하고, 중복 계산을 줄이고자 DP 알고리즘으로 품.

import sys
readline = lambda: sys.stdin.readline().strip()

# 전처리
N, TARGET_MONEY = map(int, readline().split())
coins = []
for _ in range(N):
    coins.append(int(readline()))

# dp[i] = i금액을 만드는데 필요한 최소 동전 개수
MAX = sys.maxsize
dp = [MAX] * (TARGET_MONEY + 1)
dp[0] = 0  # init

for coin in coins:
    for money in range(1, TARGET_MONEY + 1):
        if money - coin >= 0:
            dp[money] = min(dp[money], dp[money - coin] + 1)

if dp[TARGET_MONEY] == MAX:
    print(-1)
else:
    print(dp[TARGET_MONEY])

#유한개 # 가짓수 #조합

백준 #2624 동전 바꿔주기

TODO: 점화식 및 수식 이곳에

https://fieldanimal.tistory.com/46 이곳처럼 엑셀로 정리하는 것도 꽤 괜찮은 듯?

import sys
readline = lambda: sys.stdin.readline().strip()

# 1. 전처리
target_money = int(readline())
T = int(readline())
coins = []  # (money, cnt)
for _ in range(T):
    coin, cnt = map(int, readline().split())
    coins.append((coin, cnt))


# 2. tabulation
dp = [0] * (target_money + 1)
dp[0] = 1  # 의미상 1

for coin, cnt in coins:
    for money in range(target_money, 0, -1):
        for times in range(1, cnt + 1):
            # 코인 포함되어있다는 가정하에 하위 문제들의
            remain_money = money - coin * times
            if remain_money >= 0:  # 누적합
                dp[money] += dp[remain_money]
            else: # 시간초과; 더 이상 진행 불필요
                break
print(dp[target_money])

(번외편) 이 문제를 풀면서 고민했던 것들

Q. 왜 항상 coin을 고정한 상태에서 순회를 해야할까?

Q. 왜 target_money 역순으로 순회를 해야할까?

# 정답 순회 순서) coin 고정, money 역순
for coin, cnt in coins:
    for money in range(target_money, 0, -1):
    
# 오답1) money 고정
for money in range(target_money, 0, -1):
    for coin, cnt in coins:


# 오답2) money 정순
for coin, cnt in coins:
    for money in range(1, target_money + 1):