백준 16681번 등산

문제

주환이는 요즘 등산에 빠졌다. 주환이는 등산을 위해 지도를 가지고 있는데, 그 지도에는 각 지점의 높이와 갈 수 있는 다른 지점까지의 거리가 표시되어 있다.

주환이는 아침에 집에서 출발하여 등산을 갔다가, 오후 수업을 듣기 위해 고려대학교로 돌아와야 한다.

1. 주환이는 지도의 임의의 지점을 골라, 그 지점을 목표로 정한다. 집 또는 고려대학교는 목표로 선택할 수 없다.
2. 주환이가 집에서 정한 목표에 도달할 때 까지는 항상 높이가 증가하는 방향으로만 이동해야 한다.
3. 주환이가 정한 목표에 도달한 후, 고려대학교로 갈 때에는 항상 높이가 감소하는 방향으로만 이동해야 한다.
4. 주환이는 거리 1을 움직일 때 마다 D 의 체력이 소모된다.
5. 주환이는 정한 목표에 도달하면 높이 1당 E 의 성취감을 얻는다. 즉 높이가 h인 목표에 도달하면 hE의 성취감을 얻는다.

주환이는 이 등산의 가치를 (얻은 성취감) - (소모한 체력) 으로 계산하기로 하였다. 주환이를 위해 가치가 가장 높은 등산 경로를 선택해주자.

문제풀이

사용한 알고리즘 : 다익스트라

(0) 생각

 임의의 지점 x 에 도달하여 얻는 성취감은 x의 높이 * E 입니다. 즉 성취감은 x마다 고정입니다.

 x까지 도달할 때 거리에 따라 피로도가 증가하므로 거리가 최소인 것이 이득입니다.

 

 모든 지점 i에대해

    1. 집에서 i까지 올라가는 최소거리

    2. i에서 고대까지 내려가는 최소거리 ( 고대에서 i까지 올라가는 최소거리 )

 를 구해줍니다.

 답은 모든 거리 i에대해 (i높이 * E) - (1,2 두 최소거리 합 * D) 중 최대값입니다.

(1) 코드 16~21

 다익스트라 구현을 위한 priority_queue 를 만들어놓습니다.

 pair< 지점, 지점까지 걸린 거리 > 를 저장하고 거리가 짧은게 위로 오도록 합니다.

(2) 코드 38~55

 집에서 각 지점에 올라가는 최소 거리를 구합니다. ( 다익스트라 )

(3) 코드 26~74

 고대에서 각 지점에 올라가는 최소 거리를 구합니다. ( 다익스트라 )

 ( 이는 각 지점에서 고대로 내려가는 최소 거리와 같습니다. )

(4) 코드 75~81

 집과 고대를 제외한 모든 지점의 등산가치 중 최대를 구합니다.