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

---

1. 1차원 DP코드(통과O)

import sys

"""     
각 코인을 추가하여 만들 수 있는 경우의 수

		1   2   3   4   5   6   7   8   9   10
    1   1   1   1   1   1   1   1   1   1   1  			
    2   0   1   1   2   2   3   3   4   4   5         	
    5   0   0   0   0   1   1   2   2   3   4
        1   2   2   3   4   5   5   7   8   10
"""

answer = 0
n, k = map(int, sys.stdin.readline().rstrip().split())
coins = [int(sys.stdin.readline().rstrip()) for _ in range(n)]
coins.sort()
dp = [0] * (k + 1)
dp[0] = 1

for i in range(len(coins)):
    for won in range(coins[i], k + 1):
        dp[won] += dp[won - coins[i]]
print(dp[-1])

2. 2차원 DP코드(통과X)

import sys

"""     
                 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
1번 코인 사용      [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
2번 코인 사용      [1, 2, 2, 3, 3, 4, 4, 5, 5, 6]
3번 코인 사용      [1, 2, 2, 3, 4, 5, 6, 7, 8, 10]
"""
answer = 0
n, k = map(int, sys.stdin.readline().rstrip().split())
coins = [int(sys.stdin.readline().rstrip()) for _ in range(n)]
dp = [[0] * (k + 1) for _ in range(n + 1)]
for i in range(1, len(coins) + 1):
    dp[i][0] = 1
    for won in range(1, k + 1):
        # 현재 코인보다 작은 won 은 기존 값을 그대로 물려받는다.
        if won < coins[i - 1]:
            dp[i][won] = dp[i - 1][won]
        # 현재 코인을 사용한 경우와 현재 코인을 사용하지 않는 경우를 더한다.
        else:
            dp[i][won] = dp[i][won - coins[i - 1]] + dp[i - 1][won]
print(dp[-1][-1])
for i in dp:
    print(i)

---

3. 후기

dp[0] = 1을 선언해야 각 코인을 하나만 사용했을 때 초기값을 획득할 수 있다.

이 문제는 메모리 제한이 걸려있어 2차원 DP로는 시간 초과가 발생한다. 그래도 2차원 DP에 친숙해지기 위해 배낭 문제와 비슷한 느낌으로 구현만 해보았다.