9084번 동전 G5

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

그냥 갑자기 배낭 문제에 꽂혀서 쉬운거부터 해보고 있다..
이 문제는 앞에서 풀었던 문제들 보다는 약간 더 생각을 해야했다.

테이블은 같은 방식으로 생성했다. (동전의 개수) * (만들 금액 + 1) 크기의 테이블이 필요했다. 조금 더 생각이 필요했던 부분은 같은 동전이 여러번 사용될 수 있다는 점이었다. 다시 말하면, 1원, 5원, 10원을 각각 무한개를 주고 100원을 만드는 방법의 수를 구하라는 것인데 앞에서 풀었던 정말 기본적인 배낭 문제에서 물건이 하나씩만 주어졌던 것과는 조금 다르다.

그래서 dp 테이블의 의미를 다시 곱씹어보며 해결 방법을 생각해보았다.
일단 dp[ i ][ j ]는 0번째 동전부터 i번째 동전을 사용해 j원을 만드는 것이다.
기존의 배낭 문제에서는 i번째 물건을 j에 포함시킬 수 있으면 dp[ i - 1 ][ j ]와 dp[ i - 1 ][ j - (i번째 물건의 무게) ] + i번째 물건의 가치의 값을 비교해 더 큰 값을 저장했고 포함시킬 수 없다면 dp[ i - 1 ][ j ]의 값을 그대로 사용했다.
하지만 여기서는 계속 말했듯이 그대로 하면 안 된다. 위의 1, 5, 10원 예시를 다시 가져와서, 만약 30원을 1원과 5원을 사용해 만든다고 생각해보면, dp 테이블의 첫번째 줄은 1로 이미 다 채워져 있을 것이고 두 번째 줄을 채우고 있을 것이다. dp[ 1 ][ 30 ]의 자리에 들어갈 값은 dp[ 0 ][ 30 ] (1원을 사용해 30원을 만든 경우), dp[ 0 ][ 25 ] (1원을 사용해 25원을 만든 경우), dp[ 0 ][ 20 ] (1원을 사용해 20원을 만든 경우), ... dp[ 0 ][ 0 ] (1원을 사용해 0원을 만든 경우) 를 모두 더해야한다.
왜냐.. 1원만 사용해서 30원을 만들었다면 5원이 필요없고, 25원을 만들었다면 5원짜리 하나만 끼워넣으면 된다. 20원에는 5원짜리 2개, ... (반복)

다음 줄까지 넘어가서 10원까지 사용해보자.. dp[ 2 ][ 30 ]의 값을 알고 싶다.
결론부터 말하면 dp[ 1 ][ 30 ] + dp[ 1 ][ 20 ] + dp[ 1 ][ 10 ] + dp[ 1 ][ 0 ] 이다.

• dp[ 1 ][ 30 ] : 1원과 5원을 사용해 30원을 만드는 방법의 수
• dp[ 1 ][ 20 ] : 1원과 5원을 사용해 20원을 만드는 방법의 수
• dp[ 1 ][ 10 ] : 1원과 5원을 사용해 10원을 만드는 방법의 수
• dp[ 1 ][ 0 ] : 1원과 5원을 사용해 0원을 만드는 방법의 수

각각의 방법의 수를 다 더해주면 되는 것이다. dp[ 1 ][ 20 ]는 결국 10원을 1개 쓰고 나머지는 1원과 5원을 사용해 30원을 만드는 것과 같은 의미이다. 나머지도 마찬가지. dp[ 1 ][ 0 ]은 10원을 3개 쓰고 나머지는 1원과 5원으로 채우는 것인데 그러니까 당연히 1이 되어야한다.

글로 쓰려니 뭔가 정신 없게 보이는데 코드로는 훨씬 간단히 정리된다..

동전은 1원부터 10000원까지 있을 수 있고 만들 금액도 1원부터 10000원까지이다.
아무래도 반복문이 한 번 더 끼워 넣어져야 해서 범위를 많이 줄인 듯 하다.

from sys import stdin

test = int(stdin.readline())
for t in range(test):
    n = int(stdin.readline())
    coins = list(map(int, stdin.readline().split()))
    m = int(stdin.readline())
    
    dp = [[0 for i in range(m + 1)] for j in range(n)]
    
    for i in range(n):
        for j in range(m + 1):
            if i == 0: # 첫 번째 줄 처리
                if j % coins[i] == 0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = 0
            else:
                for k in range(j, -1, -coins[i]):
                    dp[i][j] += dp[i-1][k]
    
    print(dp[-1][-1])