티스토리 뷰

IOI/IOI2011

[IOI2011 Day2] Crocodile 해법

전명우 2013.07.24 01:30

문제: http://www.ioi2011.or.th/hsc/tasks/KOR/crocodile.pdf

우선, 0번 방에서 탈출 방에서 가는 것이 아닌, 탈출방에서 각 방으로 가는 방향으로 뒤집어 생각해야한다. 

$$D[i] = 악어문지기가\ 최선을\ 다\ 할때,\ 임의의\ 탈출방에서\ i번\ 방으로\ 오는\ 최소\ 시간$$

D[i] 를 위와 같이 정의하자. D[i]는 i번 방으로 올 수 있는 방들 중에 D[j]+(j번 방에서 i번 방으로 이동하는 시간)이 2번째로 작은 값을 취해야한다. 이를 해결하기 위해서는 $O(N^2)$ 방법과 $O(N lg N)$ 방법이 존재한다.

$O(N lg N)$ 방법은 힙(heap)을 이용해 다잌스트라(Dijkstra's Algorithm)를 돌리듯이 하면 된다.

코드: http://ideone.com/VyRwKZ

저작자 표시
신고

'IOI > IOI2011' 카테고리의 다른 글

[IOI2011 Day2] Parrots 문제 고찰 및 해법  (1) 2013.07.24
[IOI2011 Day2] Elephants 해법  (0) 2013.07.24
[IOI2011 Day2] Crocodile 해법  (0) 2013.07.24
[IOI2011 Day1] Race 해법  (4) 2013.07.23
[IOI2011 Day1] Garden 해법  (3) 2013.07.23
[IOI2011 Day1] Ricehub 해법  (0) 2013.07.23
댓글
댓글쓰기 폼