이번 문제는 다이나믹 프로그래밍을 통해 해결하였다. dp 리스트를 n*21의 크기로 잡은 후, n을 순회하며 연산 후 나오는 수에 해당하는 인덱스의 값에 dp에 저장된 값을 더하는 방식으로 풀이하였다. 예제 1을 예로 들면 다음과 같다.
8 3 2 4 8 7 2 4 0 8 8

• 우선 8이 가장 처음으로 입력되었으므로, dp[0][8]을 1로 갱신해준다.
• 3이 입력되었으므로, dp[0]을 순회하며 0이 아닌 경우에 해당하는 j, 즉 8에 3을 더한 결과와 3을 뺀 결과가 각각 0~20 범위에 들어갈 경우, dp[1][8+3], dp[1][8-3]에 dp[0][8]을 더해준다.
• 2가 입력되었으므로, dp[1]을 순회하며 j가 5, 11일 때 0이 아니므로 j와 2를 더하고 뺀 값을 조건과 비교하여 더해준다.

이 과정을 반복하면, dp리스트에 경우의 수가 저장된다. 따라서 점화식은 다음과 같이 나타낼 수 있다.
dp[i][j+arr[i]]+=dp[i-1][j]
dp[i][j-arr[i]]+=dp[i-1][j]
조건까지 포함해서 정의하면 다음과 같이 나타난다.

if dp[i-1][j]!=0:
	if 0<=j+arr[i]<=20:
		dp[i][j+arr[i]]+=dp[i-1][j]
	if 0<=j-arr[i]<=20:
		dp[i][j-arr[i]]+=dp[i-1][j]

• n을 입력받는다.
• arr을 입력받는다.
• dp 리스트를 n*21의 크기로 선언하고 0으로 채운다.
• dp[0][arr[0]]을 1로 갱신한다.
• 1부터 n-2까지 반복하는 i에 대한 for문을 돌린다.
  -> 21번 반복하는 j에 대한 for문을 돌린다.
  --> 만약 dp[i-1][j]가 0이 아닐 경우,
  ---> 만약 j+arr[i]가 0 이상, 20 이하일 경우,
  ----> dp[i][j+arr[i]]에 dp[i-1][j]를 더한다.
  ---> 만약 j-arr[i]가 0 이상, 20 이하일 경우,
  ----> dp[i][j-arr[i]]에 dp[i-1][j]를 더한다.
• dp[n-2][arr[-1]]을 출력한다.

Code

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