[Python] 9084번 동전 / 3067번 Coins

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

9084번: 동전

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

3067번: Coins

---

 

22/10/03

 

 

배낭 문제 중 하나인데, 1차원 배열로 풀 수 있는 배낭 문제이다.

 

이 문제는 knapsack problem 중에서도 unbounded knapsack problem에 속한다고 볼 수 있다.

 

두 문제는 완전히 동일한 문제이기에 같은 글로 엮어서 올린다.

---

 

문제 접근 방식:

 

 

DP[i] = i원을 만드는데 드는 경우의 수라고 정의하자.

 

우리의 목표는 M원을 만드는데 드는 경우의 수를 구하고 싶은 것이므로, DP[M]을 구하는 것이 우리의 목표이다.

 

코인이 여러 개 있으므로, DP[i]를 매 코인마다 갱신하는 방식으로 문제를 해결할 수 있다.

 

기본적으로, 매 코인마다 갱신하므로 어떤 coin의 값이 주어지면, DP[coin]에 해당하는 값은 1이 추가가 될 수밖에 없다.

 

예를 들자면, 1000원을 만드는데 coin의 종류가 100원과 200원, 500원이 주어져있다고 해보자.

 

그러면 맨 처음에 100원이 주어지면, 100원으로는 당연히 100원을 만들 수 있으므로 DP[100]의 값이 1 늘어날 것이다.

 

이후에는 200원이 주어지면, 200원으로 200원을 만들 수 있으므로, DP[200]의 값이 1 늘어날 것이다.

 

또한, 예를 들어 주어진 coin의 값이 500원이고, 이미 구해놓은 DP[800]의 값이 5라고 한다면, 다시 말해, 500원 이전에 주어진 동전들(100원과 200원)로 800원을 만들 수 있는 경우의 수가 5가지가 된다면, 우리는 그 경우의 수에 500원을 더함으로써, 1300원을 만들 수 있다.

 

때문에 기존에 주어진 DP[1300]은 DP[1300-500] + DP[1300]으로 갱신이 된다.

 

말로 풀어서 설명하면, 1300원을 만들 수 있는 경우의 수는 (기존에 구해놓았던 1300원을 만들 수 있는 경우의 수) + (기존에 구해놓았던 800원을 만들 수 있는 경우의 수 + 500원)으로 갱신되는 것이다.

 

이를 통해, 점화식을 다음과 같이 세울 수 있다.

 

DP[i] = DP[i-coin] + DP[i]

 

모든 코인에 대해서, 그리고 각 코인마다 위의 점화식을 통해서 DP리스트를 갱신시켜주면 답이 나온다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 9084번 동전
# DP, 배낭문제
'''
접근 방법:
DP[i] = i원을 만드는데 드는 경우의 수
DP[M]을 구하는 것이 우리의 목표

HOW?
DP[i]를 매 coin마다 갱신해준다.
'''
T = int(input())
for _ in range(T):
    N = int(input())
    coins = [0] + list(map(int, input().split()))
    M = int(input())
    DP = [0 for _ in range(M+1)]
    
    for coin in coins:
        if coin > M:
            continue
        DP[coin] += 1
        for i in range(coin+1, M+1):
            DP[i] += DP[i-coin]

    print(DP[M])