BOJ 10129: 작은 새

Link

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

• POI 2013/2014 Stage 2 3번

Tag

• dp

Time Complexity

• $O(QN)$

$N$개 나무의 높이가 주어지고, $Q$마리의 새가 1번 나무에서 N번 나무까지 날아간다. 각 새는 한번에 $k_{i}$ 그루의 나무만큼 날아갈 수 있고, 현재 위치한 나무보다 높이가 같거나 높은 나무로 날아갈때 피로감을 느낀다. 각 새의 피로감 느끼는 횟수를 최소화해야한다.

 

쿼리가 있긴 한데 $Q \le 25$이라 그냥 따로따로 풀어도 상관없다.

dp 점화식은 쉽게 나온다. $dp[i]=min(dp[j]+C)$  $(i-k \le j < i)$ ($C$는 $h[j] \le h[i]$일때 1, 아니면 0)

모든 j에 대해 고려하면 시간복잡도는 각 쿼리에 대해 $O(Nk)$이고, 시간초과다.

 

$dp[j]$값을 오름차순으로 관리하되, $dp$값이 같으면 $h$가 큰 것에 우선순위를 주면 최적인 값을 찾을 수 있다.

이때 우선순위 큐를 쓰면 $O(QNlgN)$인데, 문제 제한이 좀 빡세다.

 

따라서 deque를 이용해 최적화시켜주면 $O(QN)$에 해결할 수 있다.

Code