[백준 5557] 1학년 (python)

5557번: 1학년

---

 DP를 이용하여 풀자! 처음에 문제를 잘못 이해해서 input을 다 더하는 줄만 알았는데 마지막 값이 결과로 나오게 해야했다. 문제를 잘 읽고 풀자.

 

1. dp[0][첫숫자] = 1로 시작한다.
2. 다음 숫자마다 그 수를 더하거나 뺀것이 (j±arr[i]) 가 0이상 20 이하라면 그 전 결과값을 더해준다.
3. 마지막 수가 나오는 결과값을 출력한다.

 

import sys
input = sys.stdin.readline

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 j+arr[i] < 21:
                dp[i][j+arr[i]] += dp[i-1][j]
            if 0 <= j-arr[i]:
                dp[i][j-arr[i]] += dp[i-1][j]

print(dp[N-2][arr[-1]])