백준1126 같은탑

난이도 6/10

DP문제, 특히 난이도가 높다고 생각한다. 특히 탑 구현? 부분 즉, dp 2차원을 어떤 정보로 memoization 할것인가가 크게 걸렸다. 

나는 온전하게 문제를 풀지 못하였지만, 기억을 잃지 않으려고 포스트를 써본다.

각기 높이가 다른 블록이 여러개 주어지는데, 이것들로 두탑을 만드는데 두 탑의 높이가 같게 만든다.

그런데 그것이 최대가 되는 지점을 생각해야한다. 최적화이다.

인공지능이라는 어려운 주제를 구현하는 방법을 모르고,

쉬운 방법을 원한다면 모든 경우의 수를 다 고려하는게 좋다, 그리고 가장 큰 특성치(두 탑의 높이가 같으며 최대 높이)인 지점을 찾는것.

결국은 brute force와 그 지수복잡도를 해결하기 위한 subproblem의 만남이다. 즉 dp문제.

어떤 지점에서 subproblem이 생길까? 

우선, 블록이 주어졌을 때 탑을 만드는 경우는 다음과 같다.

1. 해당 블록을 사용하지 않는다.

2. 왼쪽에 놓는다.

3. 오른쪽에 놓는다.

상태 트리를 그려보면 다음과 같다. (여기서 n=3, a[]={2, 3, 5} )

그리고 다음에서 정확히 같은 상태가 나타난다. (3, 5, 0)과 (3, 0, 5)는 엄밀히 말하면 같은 상태이다.

또한 (1, 2, 0)과 (1, 0, 2)로 부터 내려가서 끝 상태는 합쳐서 18가지 상태가 있는데 이는 완전히 동일하다. 

왜냐하면 우리가 구하고자 하는것은 구별되는 왼쪽 오른쪽 탑의 높이가 아니라 

두 탑의 높이가 최대로 같은 높이를 구하는 것이기 때문이다. 그래서 (3, 5, 0)과 (3, 0, 5)는 다음과 같이 표현할 수 있다. (3, 5)

그렇다면 상태 저장을 어떤 정보를 주로 할까? ( 진행된 블록 수, 두 탑의 높이차) 이다.

그러므로 다음과 같이 행위를 수정하면 상태를 저장하기가 쉬워진다.

1. 해당 블록을 사용하지 않는다.

2. 높은 쪽에 놓는다.

3. 낮은 쪽에 놓는다.

상태 저장을 하며 진행하는 상태 트리는 다음과같다. 순서쌍 (n, diff)는 n번째 진행사항이며, diff는 두 탑 높이의 차이다. 

트리의 깊이가 n과 같을 때 두 탑의 높이 차가 0이 아니라면, 즉 높이가 같지 않다면, 음의 무한대를 반환한다.

우리는 높이가 같은 경우에만을 취급하기 때문이다.

두 높이의 차가 0일 때의 경우는 두 탑의 높이를 반환한다. 여기서 반환하는 방법이 신기한데 상태로 내려가는 것 바깥에 현재 두 탑의 차를 더한다.

즉, 다음과 같다. 단 이 점을 생각하자. 현재 두 높이의 차가 0이 아닐때, 다음 진행사항에서 두 높이의 차가 0이 되는 경우는 작은 탑에 해당 블럭을 놓는 경우 밖에 없다. 따라서 아래에 보는 정의는 재귀 함수가 내려갈 경우 중 하나에 불과하다.

느낀점

문제 해결법을 더욱 개선시켜 상당히 효율적으로 풀 수 있는데, 이 것 또한 알아봐야할 것같다.

역시 dp는 아직 어렵지만, 가닥이 잡히는 것 같기도하다.

소스보기

https://github.com/ingyeoking13/algorithm/blob/master/bj/p1000/1126.c