BOJ 10129 작은 새

2020. 2. 10. 04:45알고리즘 문풀/BOJ 연습

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

 

10129번: 작은 새

문제 경기과학고의 뒤뜰에는 일렬로 된 n개의 나무로 이루어진 숲이 있다. 그 중 첫 번째 나무 위에는 마지막 나무의 위로 올라가고 싶어하는 작은 새가 한 마리 있다. 그 새는 몸집이 매우 작기 때문에 한 번의 비행으로 날아갈 수 있는 거리에 한계가 있다. 만약 새가 i번째 나무 위에 있다면, 이 새는 한 번의 비행으로 i+1, i+2, …, i+k번째 나무 중 하나로 갈 수 있으며 그보다 멀리 떨어진 나무로는 가지 못한다. 또한, 작은 새에게 지금 있는

www.acmicpc.net

 

더보기

가장 먼저 드는 생각은 \(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)\) 풀이도 정확히 같다.