[DP] BOJ 9084 동전

문제

9084번: 동전

 

풀이

1. 이번 예시에서는 동전의 종류는 2원, 4원, 7원이고 이를 사용해서 11을 만드는 경우의 수를 찾아야한다. 우선 dp 테이블을 2차원 배열로 row는 가지고 있는 동전의 종류 col은 0부터 M까지로 만든다. 

 

2. 동전의 종류 중 가장 작은 값인 2를 초항으로 선택한다. 2로 0원부터 11원까지 만들 수 있는 경우의 수를 모두 입력한다. 여기서 0원을 만들 수 있는 경우의 수는 무조건 1이다. (각 동전을 사용하지 않는 경우에 0을 만들 수 있다.)

 

3. 그 다음 동전부터는 이전 동전의 경우의 수와 합쳐서 테이블을 채운다. 두번째로 작은 동전은 4원이므로 0부터 3원까지는 2원이 만들 수 있는 경우의 수와 같다. 그리고 4원부터 2원과 함께 만들 수 있는 경우의 수를 찾아 나간다.

1원 부터 3원까지는 4가 만들 수 있는 경우의 수가 없다.

4원을 만드는 경우는 4원에서 4원을 빼서 만드는 경우와 2원에서 4원을 만드는 경우를 합한 경우와 같다.

5원을 만드는 경우는 5원에서 4원을 빼서 만드는 경우와 2원이 5원을 만드는 경우를 합한 경우와 같다.

4. 2번 과정을 모든 동전에 적용하면 테이블은 다음과 같이 만들어진다.

위와 같은 논리를 통해 가장 큰 동전으로 M을 만드는 경우에 수에는 모든 동전으로 M을 만드는 경우가 포함되어있다.

따라서 가장 마지막 값을 출력하면 문제에서 요구하는 답을 내놓을 수 있다.

 

코드

import sys

T = int(sys.stdin.readline())

for _ in range(T):

    N = int(sys.stdin.readline())
    coins = list(map(int,sys.stdin.readline().split()))
    M = int(sys.stdin.readline())

    d = [[0] * (M+1) for _ in range(N)]

    for i in range(N):
        d[i][0] = 1
        for j in range(1, M+1):
            if i-1 >= 0: # 두번째 동전 부터 dp 계산
                if j >= coins[i]:
                	# 이전 동전이 j를 만드는 경우 + j에서 현재 동전을 빼는 경우의 수
                    d[i][j] += d[i][j - coins[i]] + d[i-1][j] 
                else:
                    d[i][j] = d[i-1][j]
            else: # 첫번째 동전은 dp 초기값
                if j % coins[i] == 0: # 첫번째 동전으로 만들 수 있는 값만 경우의 수 추가
                    d[i][j] += 1

    
    print(d[N-1][M])