[platinum3] 1126 [풀이안봄,분류확인] 같은 탑

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

 

처음

처음 봤을 때 이분매칭이나 다른 내가 모르는 알고리즘 일까 해서 분류를 확인했다.. 땅따먹기 문제 이후 헤매는 거에 ptsd가 와서 이제 조금 막힌다 싶으면 분류를 확인하려는 습관이 생긴거 같다.  신기한 건 dp인걸 확인하자 마자 10분정도만에 바로 풀이법이 떠올랐다;;   

 

꽤나 참신한 dp였다.  n = 50이라 비스마스크를 쓸 순 없고 애매하게 작은 수라 dp를 처음에 생각을 안하게 될 수도 있을 것같다.

 

일단 정답부터 말하자면 dp[i][ h 그동안 쌓아온 두탑의 높이 차이] =  i번째 블럭에서 h만큼의 높이차이를 만들 수 있는 지금까지 조합 중 가장 높은 조합 에서 min(top1,top2).  

0~부터 50번째 까지의 블록을 추가하는 for문안에서 0~50만 까지의 높이를 돌면서  i번째의 블록을 추가했을 때 두탑의 차이가 h이고,  이때의 두탑 높이중 최소가  dp[h] 보다 크면 dp[h]를 업데이트 하는 방향으로 가면 된다.

다음과 같은 상황에서는 어떻게 하면 될까?

 

 

 

1일때는 높이1, 높이 0 인 조합 밖에 없으므로 dp[1] = 0 이다. 

 

2번째 일때를 잘 보자. 높이 3인 블럭을 추가하는 것이다.  높이 0부터 순회한다고 했을  때 블럭3을 추가하면 높이차는 3이므로 dp[3] = 0 이다.

이번엔 높이 차이가 1일때 작은 쪽의 높이는 0 (아무블럭도 없는 경우) 이고, 이때 반대쪽에 높이3 블럭을 추가하면 높이차는 2가 된다. 또한 작은쪽 높이는 1 이므로, dp[2] = 1이 된다.

 

이번에는 높이1 블럭 위에 높이3 블럭을 쌓는 경우 높이차는 4, 작은쪽은 0 (블럭없음) 이므로 dp[4] = 0 이 된다.

 

 

 

3번째 높이5인 블럭인 경우일 때를 봐보자

이전의 i = 2 에서 dp[2] = 1이였던 경우를 생각해보자. 이번에 반대쪽에 높이5인 블럭을 추가하게 된다면 높이차는 3이되고, 작은쪽 높이는 기존의 1 에서 이전 높이차였던 2를 추가한 3이 된다. 또 기존의 dp[3] = 0 였는데, 이번에는 dp[3] = 3이 되므로   때문에 업데이트하면 된다.

이런식으로 모든 높이에 대해 i 번째 블럭을 추가했을 때 dp[높이차이]를 업데이트 해나가면 된다.

답은 i = n 번째 블럭까지 추가를 했을 대 dp[0]이 답이 될 것이다. (높이차이 = 0 : 같은 높이 )