[platinum4] [해설, 알고리즘 분류 안봄] boj1209 단조수열 만들기

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

 

 

술먹고 집에와서 착잡한 마음에 새벽에 푼 문제였다. 처음엔 아이디어성 문제인줄 알고 고민했지만 생각해보니 dp 문제였다.

처음 떠올린 아이디어는

일단 저렇게 최대로 가능한 증가수열을 만들고 밑의 포인트들은 중간값 정리로 해결하려고 했지만... 

(A,B)사이는 어떤 점이든 A - B 가 되므로, 역시나 이건 밑의 포인트가ㅣ 중간에 하나만 있을때만 가능한 공식이였다.

 

그렇다면 어떤 포인트를 그리디하게 잡을 수 있는지 고민해 보았지만 뒤에 포인트들이 어떻게 분포하고 있는지에 따라 일정한 그리디한 규칙을 유지할 수 없었다. 예컨데, 증가단조수열에서 아무리 수열을 그리디하게 낮게 잡으려고 하면 다음 포인트들이 높은 곳에 분포할 수도 있고, 그 반대일수도 있으므로 말이다.

그러면 모든 경우에 대해 생각해 봐야 할 것인데.,.. 다이나믹 프로그래밍을 써야 할 것이다.  오른쪽으로 감에 따라 마지막 포인트가 어디에 있냐로 구할 수 있을 것이다.

그런데 문제가 있다, dp[i][range]에서 range를 얼마나 해야 하느냐가 문제다. 제한조건에서 10억까지이므로 방법을 찾아야 한다.

 

 

점들을 y축에다가 두고 생각해 보자. 만약 range가 A~E 까지라고 생각해보자. (구간을 벗어난 경우는 X.  가능하면 point는 작아야 하기 때문에 A를 벗어날 수 없고, E보다 작을 순 없기 때문에 E를 벗어날 수 없다)

 

다음 point를 구간2 에 둘거라고 생각해보자. 위로는 A,B 아래로는 C,D,E가 있기 때문에 절댓값의 합을 줄이기 위해 무조건 아래로 가려고 할 것이다. 따라서 구간2에 둘것이라면, 무조건 C에 두어야 한다.  비슷한 원리로 구간3 에 둘것이라면 C에, 구간4에 둘거라면 D에 둬야 한다. 만약 구간 3에 둘 건데 중간에 다른 점 F가 있어서 F의 아래쪽에는 둘수 없는 경우가 있으면 어떻 할 것인가? 애초에 이건 전제가 잘못 됬다. F가 있다면 이미 y축상에 F가 있고,  위에처럼 구간이 다섯개가 되었을 것이다.

 

따라서 우리는 dp를 range 내의 모든 수를 계산하지 않고, point들의 y축 좌표만  고려하는 것으로 계산할 수 있게 되었다.

이 좌표들을 오름차순  H1,H2,H3,... 라고 하자.

그런데, 이렇게 하여도 O(N^3) 의 시간복잡도로 시간초과가 날 것이다. i번째에서  N * N 번 계산을 해야하기 때문이다.

그렇다면 어떻게 할 것인가? 생각을 해보니 point가 밑에 있으면 무조건 좋다. 밑에 있으면 다음에 선택할 수 있는 점들의 갯수가 많기 때문이다. 밑에 있으면 무조건 좋은데, 만약 dp[i][H1]  < dp[i][H2] 라고 생각해보자. H1이 밑에 있으면 무조건 좋은데, dp 값또한 더 작기 까지 하다. 그러면 무조건 H1에 있을 때가 좋으므로 , dp[i][H2]값은 쓸모가 없게 된다. 따라서 이런 경우에는 dp[i][H2] = dp[i][H1]으로 설정한다.이렇게 위로 올라가면 결국 위로 갈수록 dp값은 작거나 같아지게 될것이다.

결국 i번째에서 dp[i][Hk]를 생각할 때  고를 수 있는 이전의 dp  값 dp[i - 1][H1] , dp[i - 1][H2] ... dp[i - 1][Hk] 중에 dp[i - 1][Hk]를 선택하면 된다. 오름 수열 이므로 Hk 이하인것중에 골라야 하고,  여기서는 Hk일때가 가장 작기 때문이다.

이렇게 하면 시간복잡도는 O(N^2)이다.

 

이렇게 이문제에서는 dp의 범위를 점들의 y축으로만 잡으면 된다는 점과  그리디하게 i-1번째에서 가장 고를 수 있는 큰 수를 골라야 (결국 같은 H값) 을 골라야 한다는 점을 생각하기 때문에, 만만하지만은 않은 문제였다. 반대로 감소 단조수열일때는 반대로 하면 된다.

술먹고 와서 풀다가 못 풀었으면 기분도 더 안좋았을 텐데 다행히 풀고 꿀잠을 잘 수 있게 되었다.