티스토리 뷰
https://www.acmicpc.net/problem/1126
$dp[i][j] = 1 $~ $i$번 토막으로 높이가 $h1, h2$이고 $h1 - h2 = j$인 탑을 만들었을 때 $h1$의 최댓값
(단, $h1 >= h2 >= 0$)
$i$번째 토막을 포함하는경우 / 포함하지 않는 경우로 나누면 위 점화식을 해결할 수 있다.
$dp[i][j]$를 계산하는 상황을 생각해보자.
$i$번째 토막을 포함하지 않는다면 $dp[i][j] = dp[i-1][j]$이다.
$i$번째 토막을 포함한다면 $h1$에 포함되는 경우와, $h2$에 포함되는 경우로 나눌 수 있다.
먼저 $h2$에 포함되는 경우 $dp[i][j] = dp[i-1][j+h[i]]$이다.
$h1$에 포함되는 경우는 다시 두 경우로 나뉜다.
$h[i] <= j$인 경우, $dp[i][j] = dp[i-1][j-h[i]] + h[i]$이다.
$h[i] > j$인 경우, $dp[i][j] = dp[i-1][h[i]-j]] - (h[i] - j) + h[i] = dp[i-1][h[i]-j]] + j$이다.
위 세 가지 경우들 중 최댓값을 $dp[i][j]$로 정하면 된다.
최종적으로, $dp[n][0]$은 n개의 토막을 고려하여 $h1 - h2 = 0$, 즉 $h1 = h2$인 최대의 $h1$을 담게 된다.
$dp[n][0] = 0$일 경우 $h1 = h2 = 0$이므로 탑을 쌓는 것이 불가능하다. 따라서 0인지 아닌지 판단하여 -1이나 최대 높이를 출력하면 된다.
다만 점화식을 계산할 때 주의할 점은, '존재할 수 없는 경우'를 제외시켜야 한다는 것이다. ($dp[i][j] = 0$인 것과는 다르다. 이는 '아무것도 선택하지 않는 경우'에 해당한다.)
이를테면 초기 조건에서 $dp[0][0] = 0$이지만, $dp[0][i] (i >= 1)$은 존재하지 않는다.
따라서 음수 등 다른 dp값과 구별되는 값으로 지정할 필요가 있다.