백준 16235. 나무 재태크

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

16235번: 나무 재테크

 

시간 제한이 0.3초로 시간복잡도를 조심해서 풀어야 하는 문제다.

 

처음에 우선순위 큐를 이용해 풀었는데 시간초과가 나왔다.

생각해보면 이 문제를 우선순위 큐로 풀게 된다면, 한 칸에 나무 여러 그루가 있을수 있기 때문에 나무들 하나하나를 확인할때마다 우선운위 큐에서 빼내고, 다시 넣고를 반복해야하기 때문에 넣을때마다 O(logN)의 시간을 잡아먹는 우선순위큐의 사용은 부적절하다. 

 

우선순위 큐를 쓰지 않고 정렬을 사용했더니 시간초과가 나지 않고 통과했다.