239. 1학년

백준

1. 다이나믹 프로그래밍

n = int(input())
array = list(map(int, input().split()))
# dp[index번째][현재까지의 수] = 가능한 경우의 수
dp = [[0] * 21 for _ in range(n)]

dp[0][array[0]] += 1 #첫번째 숫자는 반드시 포함

for i in range(1, n - 1):
   for j in range(21):
       if dp[i - 1][j]:
            if j + array[i] <= 20: 
                dp[i][j + array[i]] += dp[i - 1][j]
            if j - array[i] >= 0: 
                dp[i][j - array[i]] += dp[i - 1][j] 

print(dp[n - 2][array[n - 1]])

• 1부터 n - 2 까지의 index를 기준으로 다음 숫자를 더하거나 뺐을 경우 0이상 20이하 일 경우에만 이전 경우의 수(dp[i - 1][j])를 더해준다.

  • j + array[i] 가 20 이하일 때

    • dp[i][j + arr[i]] += dp[i - 1][j]

  • j - array[i] 가 0 이상일 때

    • dp[i][j - arr[i]] += dp[i - 1][j]

• N - 1번째 숫자는 나와야 하는 결과이므로 N - 2 까지의 인덱스만 확인하면 된다.

• dp[N - 2][arr[N - 1]]

  • N - 2 번째 까지의 원소를 사용하여서 arr[N - 1]가 나올 수 있는 모든 경우의 수