[DP] 원하는 State를 정의하여 한 칸씩 나아가는 DP / 올바른 등식 만들기

문제링크

https://www.codetree.ai/missions/2/problems/right-equality?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

1. 핵심

• DP의 정의
  • DP[i][j] 는 i번째 숫자를 반드시 선택했을 때 i번 숫자로 ± 하여 j를 만드는 경우의 수라고 하겠다.
  • 따라서, 점화식은 DP[i][j] = DP[i - 1][j - nums[i]] + DP[i -1][j + nums[j]]
• M이 -20 부터 20이다. 그런데 '음수'는 인덱스로 접근이 어렵다. 따라서 우리는 음수를 양수로 만들어서 생각할 것이다.
  •  BASE = 20을 도입할 것이다. 
  • 그래서 DP[n][0]의 의미는 n번째 숫자를 선택했을 때 0을 만드는 경우의 수인데 실제로는 n번째 숫자를 선택했을 때 -20을 만드는 경우의 수라고 생각을 해야한다,
• 초기값 
  • DP[0][0]는 실제로 0번째 숫자를 선택했을 때 -20을 선택하는 것이므로 당연히 0이다.
  • 그렇기 때문에 0번째 숫자를 선택했을 때 0이 되는 경우의 수는 1이 되는데 우리가 BASE 20을 도입함으로써 DP에 기록될 때는 DP[0][0 + BASE] = 1이 기록이 되어야한다.
  • 경우의 수이므로 초기값이 1이 됨에 주의한다.
• 유사한 문제

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

5557번: 1학년

2. 코드(Python)

# 같은 상황: i번째를 선택했을 때, 그 전까지의 (+의 개수, -의 개수, 합)이 동일하면 같은 상황
# dp[i][j]: i번째 숫자를 선택했을 때, 숫자j를 만들 수 있는 경우의 수!
# dp[i][j] = dp[i - 1][j + num], dp[i - 1][j - num] where -20 <= j +- num <= 20
# m을 -20으로 하면 인덱스 처리가 어려움, m += 20 .. 0 <= m <= 40
# 우리가 dp[n][0] 0은 실제로 m이 -20을 의미하는 것이다..
# dp[0][0] = dp[0][20]
n, m = map(int, input().split())
base = 20
nums = [0] + list(map(int, input().split()))
inf = int(1e9)
max_range = base * 2 + 1
dp = [[0 for _ in range(max_range)] for _ in range(n + 1)]

dp[0][0 + base] = 1
for i in range(1, n + 1):
    for j in range(max_range):
        if 0 <= j + nums[i] < max_range:
            dp[i][j] += dp[i - 1][j + nums[i]] 
        if 0 <= j - nums[i] < max_range:
            dp[i][j] += dp[i - 1][j - nums[i]] 

print(dp[n][m + base])