BOJ 9084 동전문제

동전 문제

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

첫 번째 시도

동적 프로그래밍으로 풀고 싶었다.
동전의 개수 N = 2, 동전의 종류 C = [1,2], 만들어야 할 금액 M = 1000가 입력된다고 하고.

D[1]은 가능한 모든 동전을 사용해 1원을 만들 수 있는 경우의 수
D[2]은 가능한 모든 동전을 사용해 2원을 만들 수 있는 경우의 수
….
D[M]은 가능한 모든 동전을 사용해 M원을 만들 수 있는 경우의 수

여기서 D[M]을 구하는 일반화된 식을 만들어보려고 M=1인 경우부터 쭉 나열했다.

이런식으로 표를 작성했는데, 경우의 수가 중복해서 계산되는 문제가 있었다.

두 번째 시도

이상한 표만 계속 그리다가 결국 구글링..

http://blog.naver.com/occidere/220793012348 이 글이 가장 도움이 됐다. 코드는 안보고(!) 일반화하는 방법을 참고했다.

동전의 종류가 오름차순으로 주어지는 것에 가장 큰 힌트가 있었다.
동전 1, 2가 있다면

1. 동전 1원으로, 1원부터 M원까지 만드는 경우의 수를 구하고, 결과를 D[M]에 저장.
   

   

   
   

2. 동전 1원과 2원으로, 1원부터 M원을 만드는 경우의 수를 구한다. 앞 단계에서 구했던 D[M]을 재사용한다 !!
   

   

 한 마디로 앞 단계에서 사용 가능한 동전(1원)으로 M원을 만드는 경우의 수에, 현재 단계에서 새로 추가된 동전(2원)으로 M원을 만드는 경우의 수를 더한다.

최종 코드

T = int(input())

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

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

    d[0] = 1

    for coin in C:
        for m in range(coin, M + 1):
            d[m] = d[m] + d[m - coin]

    print(d.pop())