BOJ 1126 : 같은 탑

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

dp로 풀 수 있다.

dp[i][j] = i번째 블럭을 쓰고, 두 탑의 높이 차가 j일때 최대 높이

dp[i+1][j] = max(dp[i+1][j], dp[i][j]) (블럭을 사용 안할 때)

dp[i+1][j+h] = max(dp[i+1][j+h], dp[i][j]+h) (블럭을 쌓아서 높이 차이를 크게 할 때)

dp[i+1][|j-h|] = max(dp[i+1][|j-h|], dp[i][j]+max(j-h,0)) (블럭을 쌓아서 높이 차이를 작게 할 때)

 

어려워서 풀이를 보고 풀었는데 좀 많이 안해본 기술이 BOJ다른 분 코드에 있었다.

-차피 dp테이블을 채울 때 첫 인자는 현재와 다음밖에 쓰지 않기 때문에 mod2 토글링을 해서 풀 수 있다.

 

차이로 한다는 아이디어가 좀 신박하고 재밌었다. 푼지 몇 달 됬는데 아직도 기억에 잘 남는 듯 하다.

풀이