(1) K <= N인 경우
자명합니다.
(2) N < K인 경우
K보다 큰 어떤 위치 K + y에서 -y만큼 움직이는 것이 최단경로라고 가정합니다.
이때 K를 건너뛰는 2배 이동이 최소 1번은 발생해야 합니다.
그 때의 값을 M이라고 합시다.
즉, 이 경로 전체는 다음과 같은 중간지점을 지납니다.
N -> (x초) -> M -> (1초) -> 2M = K + y -> (y초) -> K
전체 경로에서 x + y + 1초가 걸립니다.
(2-1) K가 짝수인 경우
M = K/2 + y/2가 됩니다. 자연스럽게 y도 짝수입니다.
그러면 M에서 2배 이동을 하는 대신에 y/2초 동안 음의 방향으로 이동하는 경로를 생각합니다.
N -> M -> M - y/2 -> K
이 경로는 x + y/2 + 1초가 걸리고 y는 양수이므로 원래 생각한 경로보다 짧습니다.
(2-2) K가 홀수인 경우
M = (K - 1)/2 + (y + 1)/2로 생각해봅시다. 자연스럽게 y는 홀수가 됩니다.
(2-2-1) y가 1인 경우
경로는 N -> M -> K + 1 -> K이라는 뜻이 됩니다
이것이 10만 + 1을 지난다고 가정합시다.
K가 홀수이므로 K + 1은 짝수가 되어 10만 + 1이 될 수 없습니다.
M = (K + 1) / 2이므로 K보다 작습니다.
즉, 경로의 어떤 수든 10만 + 1이 되지 않습니다. 그러므로 y=1인 경로는 없습니다.
(2-2-2) y가 1보다 큰 경우
마찬가지로 M에서 2배이동하는 대신에 M - (y + 1)/2로 이동하는 경로를 생각합니다.
N -> M -> M - (y+1)/2 -> K - 1 -> K
이것은 x + (y+1)/2 + 1 + 1 초가 걸립니다.
이것은 원래 경로보다 시간이 같거나(y=3) 짧습니다.
결론: 항상 K보다 작은 쪽에서 최선의 경로를 찾을 수 있습니다.
----
뭔가 잘못된걸 적었다면 미리 사과드립니다.

pjh172839 2년 전
문제의 기본적인 풀이법은 이해했습니다. 다만 한 가지 석연치 않은 부분이 있어서 질문 글을 올립니다.
저도 그렇고 그래프 크기를 10만으로 설정한 풀이법이 많은데, 그래프 크기가 10만일 경우에 모든 테스트 케이스에 대해서 반드시 정답을 구할 수 있는지 의문이 듭니다.
그래프 크기를 10만보다 크게 설정해서 10만보다 큰 숫자를 탐색했다가 거기서 작아지는 식으로 정답이 구해지는 경우는 없을까 해서요.
이 문제의 경우 그래프 크기가 10만이면 정답이 보장된다는 것을 증명할 수 있을까요??