junodeveloper

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[..