티스토리 뷰

ICPC/2014 인터넷예선

B. Driving License

전명우 2014. 10. 7. 17:32

주어진 연료 G 안에 도착점에 최단 시간으로 도착하는 방법을 찾는 문제다. 한 칸 이동을 할 때 L 시간 만큼 걸리고, 방향을 회전할 때 마다 시간이 1 만큼 걸린다. 이 문제에서 아래 방향과 오른쪽 방향으로만 움직일 수 있으므로, 각 위치까지 가는 시간은 여태까지 회전한 회수에 따라 결졍 된다. 즉, r행 c열에 있는 칸까지 k번 회전하였다면 걸린 시간은 총 ((r-1)+(c-1))*L + k 이다. 


따라서, D[r][c][k][d]=현재 위치는 r행 c열, 회전한 회수는 k, 현재 바라보는 방향은 d 일 때 최소 연료 사용량이라 정의하고 Dynamic Programming 을 하면 된다. 시작점에서 도착점까지 이동할 때 방문하는 지점은 많아야 199개 이며, 각 지점에서 회전을 2번 이상하는 것은 비효율적이므로 최대 회전 회수는 200번 정도라고 생각할 수 있다. 시간복잡도는 O(N^3) 이다.


'ICPC > 2014 인터넷예선' 카테고리의 다른 글

G. Mutation  (0) 2014.10.08
E. Highway  (0) 2014.10.07
D. 헨리  (0) 2014.10.07
C. 그리드 그래프  (2) 2014.10.07
A. ACM 호텔  (0) 2014.10.07
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함