[BOJ|Python] 백준 5557 1학년

문제

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

5557번: 1학년

풀이

#중간에 나오는 수가 모두 0 이상 20 이하이어야 한다

# 백준 5557

N = int(input())
List = list(map(int,input().split()))
DP= [[0 for _ in range(21)] for _ in range(N+1)]

for i in range(N):
    if i==0:
        DP[i][List[0]] = 1
    else:
        for j in range(21):
            if DP[i-1][j]:
                if 0<=j+List[i]<=20 :
                    DP[i][j+List[i]] += DP[i-1][j]
                if 0<=j-List[i]<=20 :
                    DP[i][j-List[i]] += DP[i-1][j]


print(DP[N-2][List[N-1]])

간단한 0~20 까지의 값을 계속해서 메모이제이션 하는 문제이다. 차례대로 바로 전에 나온 값들을 이용해서 +/-을 수행한 후 해당 값을 갱신해주면 된다.