pjh172839   2년 전

문제의 기본적인 풀이법은 이해했습니다. 다만 한 가지 석연치 않은 부분이 있어서 질문 글을 올립니다. 

저도 그렇고 그래프 크기를 10만으로 설정한 풀이법이 많은데, 그래프 크기가 10만일 경우에 모든 테스트 케이스에 대해서 반드시 정답을 구할 수 있는지 의문이 듭니다.

그래프 크기를 10만보다 크게 설정해서 10만보다 큰 숫자를 탐색했다가 거기서 작아지는 식으로 정답이 구해지는 경우는 없을까 해서요. 

이 문제의 경우 그래프 크기가 10만이면 정답이 보장된다는 것을 증명할 수 있을까요??

protarie   2년 전

(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보다 작은 쪽에서 최선의 경로를 찾을 수 있습니다.

----

뭔가 잘못된걸 적었다면 미리 사과드립니다.

wider93   2년 전

a-> 2a->2a-1->2a-2보다 a->a-1->2a-2가 빠르기 때문에 10만보다 큰 짝수는 도중에 2배 연산을 통해 거칠 필요가 없게 됩니다.

댓글을 작성하려면 로그인해야 합니다.