BOJ 10129 작은 새

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

10129번: 작은 새

 

가장 먼저 드는 생각은 \(dp[i]\)를 "\(i\)번 나무에 도달하기 위해 느끼는 피로감의 횟수"로 정의하는 것이다. 점화식은 아래와 같다.

$$ dp[i] = \min_{i - k \le j \le i} dp[j] + \chi(h[j] \le h[i]) $$

단, \(\chi(x)\)는 indicator function. True면 1이고 False면 0인 아이다.

 

그러면 나무의 높이마다 deque을 만들고, Segment Tree 등의 자료구조를 이용하면 \(O(n\log n)\)에 DP table을 모두 채울 수 있다. deque을 이용한 DP 최적화 (Sliding Window)가 사전 지식.

 

하지만 제한이 \(O(qn\log n)\)풀이를 시간 초과 내고 싶다는 의지로 불타고 있는 것을 알 수 있다.

 

이 문제를 해결하기 위한 핵심 관찰은, dp[i]를 결정하기 위해 참조해야 하는 \((dp[j], h[j])\)값이 일종의 Partial Order를 이룬다는 것이다.

다시 말해, \(j_{1}\)과 \(j_{2}\) 중 dp값이 낮은 것이 더 좋고, dp값이 같다면 h가 큰 것이 더 좋다.

따라서 deque에 dp값들을 밀어넣을 때 h까지 고려해서 deque의 front에 가장 좋은 값이 위치하도록 할 수 있다.

이 값을 \((dp[j^{*}], h[j^{*}])\)라고 하자.

 

그렇다면, 이 경우 dp[i]는 h[j*] <= h[i]라면 dp[j*] + 1, 그렇지 않다면 dp[j*]가 된다는 것을 확인할 수 있다.

따라서 dp[i]를 \(O(1)\) 시간에 구할 수 있고, 총 \(O(qn)\) 시간에 문제를 풀 수 있다.

 

17018 Redistricting의 \(O(n)\) 풀이도 정확히 같다.