[백준 5557 1학년 문제] PYTHON

 

이 문제를 아무 생각없이 덧셈 뺄셈을 할 때마다 배열에 추가하며 풀면 최대 2의 100승 크기의 배열이 나온다.

하지만 이 문제의 조건에는 셈을 진행하며 중간에 0 미만 or 20 초과는 셈에서 제한다는 조건이 있다.

따라서 Nx20 크기의 배열을 만들어 N-1의 숫자를 N으로 옮기는 방식으로 풀면 쉽게 해결할 수 있다. 

 

t = int(input())
gd = list(map(int, input().split()))
dp = [[0]*21 for _ in range(t)]

answer = gd.pop()
dp[0][gd[0]] = 1

for i in range(1, t-1):
    for j in range(21):
        if dp[i-1][j]:
            if j-gd[i] >= 0:
                dp[i][j-gd[i]] += dp[i-1][j]
            if j+gd[i] <= 20:
                dp[i][j+gd[i]] += dp[i-1][j]

print(dp[t-2][answer])