[알고리즘/백준] 2293번 : 동전 1(python)

다차원 리스트로 풀려고 했는데 너무 리스트가 커져서 다른 방법으로 풀었다.

1로 만드는 경우
2로 만드는 경우... 이런 식으로 나눠서 풀었고...

만약 1과 2로 3을 만들려면
111/ 1+2 이렇게 만들면 된다.
이 경우는 1로 3을 만드는 경우에 2로 만드는 경우를 추가한것
따라서 현재 코인 - 동전을 해서 더해주면된다.
dp[coin] += dp[coin - 현재 코인]

import sys
input = sys.stdin.readline


def sol():
    n, k = map(int, input().split())
    dp = [1] + [0] * k
    for _ in range(n):
        c = int(input())
        for j in range(c, k + 1):
            if dp[j - c] == 0:
                continue
            dp[j] += dp[j - c]
    print(dp[-1])
sol()