티스토리 뷰
주어진 연료 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 |
B. Driving License (1) | 2014.10.07 |
A. ACM 호텔 (0) | 2014.10.07 |
댓글
-
전지환 안녕하세요 저는 알고리즘을 공부하고있는 대학생입니다.
알고리즘을 공부하면서 이 문제와 같은 문제를 풀어보던 중에 알고리즘과 적은 데이터 샘플에서는 정상적으로 아웃풋이 나왔으나,
최대값에 가까운 큰 입력값에는 실행시간이 너무길어지는 문제가 발생해서 해결책을 찾아보던 중에 블로거님의 코드를 보게 되었습니다.
몇일을 고민하면서 짰던 제 코드와 비교해서 너무나 짧고 간단하게 실행된다는것에 적잖이 충격을 받았습니다 ㅠㅠ
몇시간 정도 블로거님의 코드를 풀어보려고 하였으나 알것같으면서도 명쾌하게 풀어지지는 않아서 부탁 하나 드릴려고합니다ㅠ
괜찮으시다면 저 조건문들의 의미들을 조금 풀어서 설명해주실수 있는지 부탁드립니다. 2018.08.21 23:10 신고
공지사항
최근에 올라온 글
- Total
- 123,707
- Today
- 3
- Yesterday
- 87
링크
TAG
- Splay Tree
- USACO
- majority
- ioi
- BOI 2009
- moore
- z-trening
- Greedy Method
- Algorithm
- Divide & Conquer
- BOI 2001
- IOI2011
- optimization
- Boyer
- Dijkstra
- Boyer-Moore Majority Vote Algorithm
- idea
- vote
- IOI2014
- TRIE
- IOI2012
- Parametric Search
- IOI2013
- HackerRank
- BOI
- Dynamic Pramming
- Tree
- Knuth Optimization
- Segment tree
- dynamic programming