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

---

1. 코드

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)]
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차원 DP테이블 풀이"""
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)

---

2. 후기

이 문제는 1차원 리스트를 사용해야만 풀 수 있다. 왜냐하면 이 문제의 메모리 제한이 4MB로 제한되어있기 때문이다. 2차원 DP 테이블을 구성하면 메모리 초과가 발생하여 통과할 수 없다. 물론 이 문제는 1차원 리스트를 사용하는 쪽이 더 효율적인 풀이가 가능하다.

dp[0] = 1 을 통해 dp[won - coins[i]] 코드에서 각 1, 2, 5를 한 번만 사용한 횟수인 1을 얻을 수 있다.

2차원 리스트를 사용한 코드는 배낭 구성 문제와 비슷한 형태를 가진다. 코인의 가짓수 + 1 길이의 행을 가지고 원을 열로 가지는 DP 테이블을 사용한다. 0번째 리스트는 모든 값이 0으로 초기화되어 있는 리스트이고, 1번째 리스트부터는 각각 코인 1, 2, 5 를 추가했을 경우를 고려한 리스트이다.