jng6017   1년 전

최소한의 연료 소비량으로 시작지점에서 도착지점에 가고 싶어한다.

사용하는 차량들이 소비하는 연료의 양을 측정할 떄는 다음과 같은 방법을 사용한다.

지역마다 높이가 주어지고 이동 할 칸의 높이에 따라 다음과 같이 연료 소비량이 주어진다. (반드시 상하좌우로만 움직일 수 있다.)

현재 위치의 높이 < 이동할 곳의 높이 --> (이동할 곳의 높이 - 현재 높이)^2

현재 높이 = 이동 높이 --> 1

현재 높이 > 이동 높이 -> 현재 높이 - 이동 높이

정사각형으로 된 칸으로 이루어 져있으며 출발지점과 도착 지점이 주어질떄 최소의 연료만을 소비하여 갈 때 최소 연료 소비량을 구하여라.

지도 가로 세로 크기 1<n(가로),m(세로)<1000가 주어진다.

m줄에는 n개씩 지역 높이가 주어진 후 출발지점과 도착지점이 주어진다.


/////////////////////////////////////////////////

O(ElogV)가 priority_queue를 이용 한다고 하여 priority_queue를 이용하여 짜보았습니다.

그런데 처음에 index트리를 이용해 최솟값을 구할때보다 더 오래 걸리네요... 어디가 잘못되었는지 가르쳐주세요 ㅠㅠ

크기가 1000이라서 O(ElogV)로 짤려는데 둘 다 1초 안에 안 나오네요 ㅠㅠ...

ex)

3 3

5 7 8

10 10 13

12 13 15

1 1

3 2

//////

22


appa   1년 전

제 컴퓨터에서는 릴리즈(Release) 모드로 실행시켰을 때, 최대 크기 데이터에서(시작점은 (1,1) 도착점은 (1000, 1000)) 200ms(0.2초) 정도 밖에 걸리지 않습니다.

appa   1년 전

jng6017   1년 전

릴리즈 모드랑 디버깅 모드가 차이가 되게 많이 나네요.. 질문에 매번 답변해 주셔서 감사합니다.

댓글을 작성하려면 로그인해야 합니다.