100,000은 짝수이지만, 15는 홀수이기 때문이 아닐까요?

직접 짜보지는 않았지만 각 시작점에 대해 나머지 모든 위치까지의 거리를 수빈이의 위치를 100000으로 제한했을 때 / 200000으로 제한했을 때 구해보고 답이 다른 경우가 있는지를 확인해보면 O(N^2)에 정당성은 확인이 가능할거고,

말씀하신대로 음수로 가는건 당연히 비효율적일텐데 100000을 넘어가는건 가능할수도 있지 않냐하는 생각이 들 수도 있습니다.

그런데 i) +1로 100000을 탈출하는건 당연히 비효율적이고

ii) x2로 100000을 탈출한다면 언젠가는 -1을 해야할거고, 그러면 사실 -1을 먼저하고 x2를 해서 100000 안에 계속 머무는게 횟수를 줄이는 관점에서 더 도움이 될테니 결론적으로 이동 범위를 100000으로 제한해놓고 계산해도 답이 잘 나온다고 대략적으로 생각을 했습니다.

ii)에서 적은 논리의 유일한 고려사항은 x2를 한 후 -1을 딱 1번만 하는 경우가 최적해인 상황인데, 수의 범위가 짝수일 때에는 다행히 문제가 되지 않습니다만 적으신대로 100000이 아니라 15와 같은 홀수였다면 반례가 쉽게 나옵니다.

개인적으로 생각할 때에는, 이게 논리적으로 생각하니 100000 안에서 움직여도 답이 잘 나오는 상황이었지만 문제를 푸는 입장에서는 적어도 음수로 넘어갈 일은 없다 / 200000을 넘어갈 일은 없다 까지만 관찰한 후 0에서 200000을 범위로 두고 풀이를 하는게 조금 더 자연스러웠을 것 같습니다.

두분 모두 답변 감사드립니다.

짝수, 홀수로는 생각을 못했는데 새롭게 생각해볼 수 있었습니다.

또한 방문 가능한 최대 범위에 대해서도 다시 고려해보게 됐습니다.