[BOJ/백준] 5557 1학년

N = int(input())

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

dp[0][arr[0]] = 1
for ind in range(1,N-1):
    for prev_num in range(21):
        if dp[ind-1][prev_num]:
            for new_num in [prev_num+arr[ind],prev_num-arr[ind]]:
                if 0<=new_num<=20:
                    dp[ind][new_num] += dp[ind-1][prev_num]

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

매번 어려운 DP 문제이다. 

 

여기서 제일 헷갈렸던것은 인덱스였다. 

먼저 dp의 행은 주어진 입력의 몇번째 index에서의 행해진 것인지 나타낸다.

그리고 열은 이 문제는 0~20 사이의 값만 있으므로, 21개의 열을 미리 만들어줬다.

 

먼저 dp를 0으로 초기화 시킨다.

 

그리고 dp[0][arr[0]] = 1로 초기화 한다.

 

가장 첫번째 숫자는 무조건 더해져야하기 때문이다.

그리고 그 다음부터는 0~21 까지를 prev_num으로 반복문을 돌리고 현재 ind의 arr값과 더했을때

0~20 사이이면 현재 ind의 새로운값에 더해주면 된다.

 

그리고 이 모든 행위는 N-2번 인덱스에서 종료되기 때문에, 출력할때 [N-2][arr[-1]]을 해주도록 하자.