[백준 / BOJ] 2158 산악자전거

문제

출처 : www.acmicpc.net/problem/2158

2158번: 산악자전거

R*C 행렬이 주어지고, 각 칸마다 높이가 주어진다.

현재 높이A에서 높이 B로 이동할때, 속력이 (2^(A-B))배로 변한다.

 

(R,C) 위치에 도달하는 최소시간을 구하는 문제다.

 

풀이

다익스트라로 풀리는문제다.

목적지에 도달할때, 다른 경로로 뺑돌아서 (속력을 높인후) 도착하는 경우가 더 빠를수 있기때문에, 다익스트라로 풀어야한다.

 

구현은 일반적인 다익스트라에 속력을 계산해주는걸 추가하면된다.

 

주의할점이 현재 (y,x)에 도착한 도달시간이 최소라해도 속력은 최소가 아니라 마지막답이 바뀔수있는데, 예를들어, i위치에 가장 빨리 오지못했더라도, 갖고 있는 속력은 더 높기때문에, i+1위치에 더 빠르게 갈수있다. 따라서, check배열을 <도달시간, 도달속도>의 형태로 선언하고 만약 도달시간이 같다면, 도달속도가 더 높은것을 저장해줘야한다. (처음에 받은 틀렸습니다가 이것때문인듯)

 

처음엔, (y,x)에 도달하기 까지의 시간이 더 오래걸리지만, 갖고있는 도달속도가 더 빠른경우가 있을수있을것이라 생각했는데, 그런경우는 있을수없다. (y,x)에 도달하기 이전 위치부터 항상 비교를 해가며 업데이트 해주기때문에, 결국 더 늦게도착하는것은 속도가 더 느린경로이다.

 

속력의 최대값이 1,000,000까지 갈수있어서 float이 아닌 long double로 풀어야한다.

 

절대/상대 오차범위가 10^-2라서 소수점 두번째까지 반올림해서 출력하면된다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/2158%20%EC%82%B0%EC%95%85%EC%9E%90%EC%A0%84%EA%B1%B0/main.cpp

devxb/JJUNalgo