티스토리 뷰

ICPC/2014 인터넷예선

B. Driving License

전명우 2014.10.07 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
B. Driving License  (1) 2014.10.07
A. ACM 호텔  (0) 2014.10.07
공유하기 링크
댓글
  • 프로필사진 전지환 안녕하세요 저는 알고리즘을 공부하고있는 대학생입니다.
    알고리즘을 공부하면서 이 문제와 같은 문제를 풀어보던 중에 알고리즘과 적은 데이터 샘플에서는 정상적으로 아웃풋이 나왔으나,
    최대값에 가까운 큰 입력값에는 실행시간이 너무길어지는 문제가 발생해서 해결책을 찾아보던 중에 블로거님의 코드를 보게 되었습니다.
    몇일을 고민하면서 짰던 제 코드와 비교해서 너무나 짧고 간단하게 실행된다는것에 적잖이 충격을 받았습니다 ㅠㅠ
    몇시간 정도 블로거님의 코드를 풀어보려고 하였으나 알것같으면서도 명쾌하게 풀어지지는 않아서 부탁 하나 드릴려고합니다ㅠ
    괜찮으시다면 저 조건문들의 의미들을 조금 풀어서 설명해주실수 있는지 부탁드립니다.     2018.08.21 23:10 신고
    댓글주소 수정/삭제 댓글쓰기
댓글쓰기 폼
1 ··· 58 59 60 61 62 63 64 65 66 ··· 120