[Python][백준] 9084. 동전 / DP, 배낭 문제 (G5)

🔗링크 :  

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

---

➕ 문제 풀기 전 

먼저 동전 문제를 풀기 전에 아래 예시를 이해해보자.  

1,2,3원으로 7원까지의 만들 수 있는 경우의 수이다. 

    (0)  (1)  (2)  (3)  (4)  (5)  (6)  (7)  
1:  0     1    1    1     1     1    1    1
2:  0     1    2    2     3     3    4    4
3:  0     1    2    3     4     5    7    8

 

먼저 1원부터 시작한다. 

오직 1원으로 1~7원을 만들 수 있는 경우의 수는 모두 1이다.

이제 2원과 3원으로 가면 위와 같은 경우의 수가 나온다. 

(해당 경우의 수는 하나 하나 직접 찾아서 써야 한다.)

 

이렇게 적절히 경우의 수를 만들면, 이제 규칙(점화식)을 찾으면 된다.

점화식을 찾을 때 해당 조건을 유심히 본다. 

(1원 경우의 수에서 1,2원 경우의 수로 넘어갈 때 2가 조건이다.)

 

이런 관점에서 보면,  dp[i] = dp[i-n] + dp[i] 가 된다. 

 

여기서 각 n원 코인에서 n번째 인덱스는 이 규칙에 해당되지 않는데,

이 경우 초기값으로 따로 조건을 추가해주면 된다.

해당 n 인덱스를 보면 dp[i] + 1 이 되는 것을 알 수 있다.

 

자, 이제 동전 문제를 풀 수 있는 모든 무기들이 있다.

이거를 코드로 구현하면 된다.

 

🗒️파이썬 코드 풀이

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N = int(input())
    coin = list(map(int,input().split()))
    M = int(input())

    dp = [0] * (2*M+2)

    for c in coin :
        dp[c] += 1 
        for i in range(c+1,2*M-1):
            dp[i] = dp[i-c] + dp[i]

    print(dp[M])

 

 

1. 입력으로 주어진 값은 T, N, coin 리스트, M 을 받아준다. 

 

2. dp의 크기는 넉넉하게 설정했다. (자꾸 인덱스 에러 발생 ...)

 

3.  for문을 통해 하나 하나 코인들의 dp 리스트를 갱신해준다.

 

4. 특이점(초기값) c 인덱스를 + 1로 업데이트 한다.

 

5. 위에서 만든 dp 식을 작성해준다. 

 

 

📌 문제 코멘트 

이 문제를 진짜 잘 이해하면 앞으로 나올 DP 문제에 대한 자신감이 생긴다.

결국에 DP는 특이점(초기값)을 잘 설정하고 점화식을 찾아주면 된다. 

 

이 문제를 잘 풀었다면, 이와 비슷한 백팩(Knacksap)문제도 꼭 같이 풀어보자.

(백팩 문제는 2차원 DP를 세팅해줘야한다.)

→ 왜 1차원은 DP는 안되는지도 다룰 예정 ! 

 

---

📚문제

우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다.

동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 동전의 가지 수 N(1 ≤ N ≤ 20)이 주어지고 두 번째 줄에는 N가지 동전의 각 금액이 오름차순으로 정렬되어 주어진다. 각 금액은 정수로서 1원부터 10000원까지 있을 수 있으며 공백으로 구분된다. 세 번째 줄에는 주어진 N가지 동전으로 만들어야 할 금액 M(1 ≤ M ≤ 10000)이 주어진다.

편의를 위해 방법의 수는 231 - 1 보다 작고, 같은 동전이 여러 번 주어지는 경우는 없다.

출력

각 테스트 케이스에 대해 입력으로 주어지는 N가지 동전으로 금액 M을 만드는 모든 방법의 수를 한 줄에 하나씩 출력한다.

예제 입력 1 복사

3
2
1 2
1000
3
1 5 10
100
2
5 7
22

예제 출력 1 복사

501
121
1