[python] 백준 5557 1학년

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

5557번: 1학년

문제 해결

• 이전 항들의 영향을 받는다. 이전 항들까지 더하기, 빼기를 이용해서 만들 수 있는 것은 0이상 20 이하여야 한다.
• dp로 가지수를 만들수 있다. dp[i][j]를 j-1번째 항까지 더하기 빼기를 이용해서 i를 만들 수 있는 가지수를 나타낸다.
• dp[A[n-1]][n-2] 의 값을 구하면 된다. 

 

CODE

import sys
input = sys.stdin.readline
n = int(input())
A = list(map(int,input().split()))
dp = [[0]*n for _ in range(21)]
dp[A[0]][0] = 1
for i in range(1,n-1):
    for j in range(21):
        if j + A[i] <= 20:
            dp[j+A[i]][i] += dp[j][i-1]
        if 0<=j-A[i]:
            dp[j-A[i]][i] += dp[j][i-1]
print(dp[A[-1]][n-2])