boj 1126 : 같은 탑

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

1126번: 같은 탑

 

DP 냄새가 강하게 나는 문제이다.

 

낮은 탑 높이의 최대값을 f(idx, diff)로 두면.

아래와 같이 점화식을 세울 수 있다.

 

1. f(-1, 0) = 0
2. f(idx, diff) = max( [1], [2], [3])
    2-1. [1] : f(idx - 1, diff)
    2-2. [2] : f(idx - 1, diff + a[idx]) + a[idx]
    2-3. [3] : f(idx - 1, diff - a[idx]) + abs(min(diff - a[idx], 0) )

2-1 : idx번째 블록을 사용하지 않는 경우

2-2 : idx번째 블록을 낮은 탑에 놓았는데, 여전히 낮은 탑이 높은 탑보다 낮을 때

2-3 : (생각할 거리가 많은 부분이다.) 두가지 경우의 수가 있다.

(1) diff - a[idx] >= 0 :  idx번째 블록을 높은 탑에 놓은 경우.

    => f(idx - 1, diff - a[idx])

(2) diff - a[idx] < 0 : idx 번째 블록을 낮은 탑에 놓았는데, 높은 탑보다 더 높아진 경우.

    => 이 경우, 낮은 탑과 높은탑이 서로 바뀌면서 값의 증가가 발생한다.

    => f(idx - 1, diff - a[idx]) + a[idx] - diff

 

이 점화식으로 N * height 시간에 풀린다.

 

점화식을 아래와 같이 쉽게 세우면

[쉬운 점화식 1] f(idx, left_height) = right_height

[쉬운 점화식 2] f(idx, diff) = {left_height, right_height} ( * diff = left_height - write_height )

수식과 코드는 조금 덜 아름답겠지만...

직관적인 수준에서 코드를 짤 수 있으므로, 고민은 덜해도 될 것 같다.

 

코드