[BOJ]16681번: 등산

 

문제: https://www.acmicpc.net/problem/16681

---

hororo님 풀이를 참고하여 문제를 해결하였습니다. (https://hororolol.tistory.com/3)

 

출발점 1과 도착점 N을 각 각 출발점으로 두 개의 다익스트라를 돌려봅니다.

 

첫 번째 다익스트라. 1 => 나머지 노드

두 번째 다익스트라. N => 나머지

 

1 => 나머지 노드의 경로는 계속 높이가 상승해야 하므로 높이가 상승하는 방향으로 다익스트라를 돌립니다.

N => 나머지 노드로의 경로는 내려올 때의 문제 조건을 반대로 해석하면 이 역시 높이가 상승하는 방향입니다.

 

이렇게 두 개를 돌리고 이 두 정보를 활용하여 최댓값을 구하면 됩니다.

for (int K = 1; K < N-1; ++K)
{
    //max({출발점에서 K노드로 가는 경로} X 성취감 - {K노드에서 도착점으로 가는 경로} X 체력소모)
}

 

추가로 주의할 점은 수가 INT 범위를 넘어설 수 있다는 점입니다.

---

코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ16681.cc