[백준-5557] 1학년

풀이

나는 2개의 list를 이용해서 문제를 풀었다. 하나는 i인덱스 까지 계산했을 때 나오는 수들을 인덱스로 하여 값을 i로 하는 리스트이고 이를 dp라고 하겠다.
예를 들어 2번인덱스 까지 계산한 값들이 1,4,5라면 dp[1]=2,dp[4]=2,dp[5]=2이다.
그다음 3번인덱스까지 계산했을 때는 dp[j]=i인 j값들을 찾고(1,4,5) j들에다가 3번인덱스를 더하고 뺀 값을 다시 dp의인덱스로 하여 그값을 3으로 한다.
다른 리스트는 i번 인덱스까지 계산했을 때 나오는 값들의 개수를 저장하고 이 리스트를 dp2라고 하면 위의 예시에서 2번인덱스까지 계산했을 때 dp2[1]=1,dp2[4]=1,dp2[5]=1 이고 나머지는 0이다. 그다음 3번인덱스를 k라고하면
임시로 tmp에다가 개수를 저장하고(tmp[1+k]+=dp2[1]...), dp2=tmp로 바꿔준다.

코드

import sys
input = sys.stdin.readline

n=int(input())
nums=list(map(int,input().split()))

dp=[0]*21

dp2=[0]*21
dp2[nums[0]]=1

for i in range(1,n-1):
    tmp=[0]*21
    li=[]
    for j in range(0,21):
        if dp[j]==i-1:
            if j+nums[i]<=20:
                li.append(j+nums[i])
                tmp[j+nums[i]]+=dp2[j]
            if j-nums[i]>=0:
                li.append(j-nums[i])
                tmp[j-nums[i]]+=dp2[j]
    for j in li:
        dp[j]=i
    dp2=tmp
print(dp2[nums[-1]])

수행시간: 72ms