무등산 등반 timer 1s memory 1024MB

전남대학교는 광주를 대표하는 지방 거점 국립대학이다. 전남대학교에서 대중교통으로 갈 수 있는 곳이 많은데, 그 중에는 광주 지역의 명산인 무등산이 있다. 평소 산을 좋아하는 근성은 3주 간의 기초군사훈련으로 단련된 자신의 체력을 자랑하기 위해 친구들과 함께 무등산에 오를 것을 결심했다.

근성은 무등산에 오르기 이전, 무등산의 높이 정보가 적힌 지도를 입수했다. 무등산은 지도에서 세로로 N칸, 가로로 M칸인 직사각형 격자 형태로 나타난다. 지도의 가장 왼쪽 상단은 (1, 1), 가장 오른쪽 하단은 (N, M)으로, 근성과 친구들은 지도의 (x, y) 위치에서 등반을 시작한다.

무등산의 각 칸에서는 시간을 소모하여 상하좌우로 인접한 칸 중 하나로 이동할 수 있다. 이때, 이동하는 칸의 높이 차이에 따라 이동 시간이 다르게 걸리거나 이동할 수 없는 칸이 생긴다.

• 높이 차이가 나지 않는 칸으로 이동할 때, 1분의 시간이 소모된다.

• 높이가 더 높은 칸으로 이동할 때, 두 칸의 높이 차이 1당 a분의 시간이 소모된다.

• 높이가 더 낮은 칸으로 이동할 때, 두 칸의 높이 차이 1당 b분의 시간이 소모된다.

• 높이 차이가 c보다 더 큰 칸으로는 이동할 수 없다.

근성이 가야 할 무등산 정상은 지도에서 높이가 가장 높은 칸이며 유일하다. 근성이 입수한 정보를 활용해 무등산 정상까지 도달하기 위한 최소 시간을 구해보자.