Jump Game

가장 직접적인 방법은 직접 해 보는 것입니다. 인덱스 0에 서서 점프할 수 있는 모든 착지 지점을 하나씩 시도합니다. 각 착지 지점에서도 똑같이 반복합니다. 어떤 경로에서든 마지막 인덱스에 도달하면 답은 true입니다. 모든 경로가 막다른 곳에 이르면 false입니다.

첫 번째 예시에서 인덱스 0에는 2가 있으므로 인덱스 1과 인덱스 2를 시도합니다. 인덱스 1에는 0이 있어 막다른 곳이므로, 되돌아가 인덱스 2를 시도합니다. 인덱스 2에는 3이 있고 인덱스 5인 마지막 인덱스에 도달하므로, 탐색은 true로 끝납니다.

모든 경로를 살펴보기 때문에 이 탐색은 정확합니다. 하지만 이것이 바로 문제이기도 합니다. 이미 탐색한 인덱스를 기억하지 않으므로, 그 인덱스에 도달하는 경로마다 같은 인덱스를 다시 탐색합니다. 답이 false인 경우에는 모든 경로를 배제해야 합니다. [4, 3, 2, 1, 0, 5]에서는 0 앞에 있는 모든 인덱스가 0에 도달할 수 있어, 0에 이르는 서로 다른 경로가 8개입니다. 이러한 인덱스가 30개라면 경로가 5억 개를 넘으며, 가장 큰 테스트에는 요소가 10,000개 있습니다. 이렇게 긴 경로는 일부 언어에서 호출 스택 오버플로도 일으킵니다. Python은 기본적으로 중첩 호출이 1,000회에 이르면 중단합니다.

위의 탐색은 "인덱스 j에서 끝까지 갈 수 있는가?"라는 같은 질문을 계속 반복합니다. j에 대한 답은 바뀌지 않으므로, 한 번 계산해서 저장하면 됩니다. 어떤 인덱스에서 마지막 인덱스까지 갈 수 있으면 그 인덱스를 양호하다고 하겠습니다. 마지막 인덱스는 양호합니다. 그 외의 인덱스 i는 도달할 수 있는 인덱스, 즉 i+1부터 i+nums[i]까지의 인덱스 중 하나 이상이 양호하면 양호합니다.

각 인덱스는 오른쪽에 있는 인덱스에만 의존하므로, 테이블 good을 오른쪽에서 왼쪽으로 채웁니다. 첫 번째 예시에서 인덱스 5는 양호합니다. 인덱스 4의 값은 0이므로 양호하지 않습니다. 인덱스 3에서는 인덱스 4에만 도달할 수 있으므로 양호하지 않습니다. 인덱스 2에서는 인덱스 3, 4, 5에 도달할 수 있고, 5가 양호하므로 2도 양호합니다. 인덱스 1의 값은 0이므로 양호하지 않습니다. 인덱스 0에서는 1과 2에 도달할 수 있고, 2가 양호하므로 답은 true입니다.

이제 각 인덱스의 상태는 한 번만 결정하지만, 결정하는 과정에서 여전히 최대 n개의 셀을 검사할 수 있습니다. [9998, 9997, …, 1, 0, 7]에서는 모든 인덱스가 0에 도달할 수 있지만 그 너머에는 도달할 수 없으므로, 각 인덱스는 전체 범위를 검사하고도 양호한 인덱스를 찾지 못합니다. 원소가 10,000개일 때 검사 횟수는 약 5 × 10^7회이며, 가장 큰 테스트는 이와 같은 방식으로 구성되어 있습니다. 작업량은 길이의 제곱에 비례해 증가하므로, 이러한 테스트에서는 시간 초과가 발생합니다.

경로가 아니라 도달할 수 있는 인덱스를 살펴보세요. 인덱스 i에서는 i+1부터 i+nums[i]까지의 모든 인덱스에 도달할 수 있으며, 그 사이에 빠지는 인덱스는 없습니다. 따라서 인덱스 i에 도달할 수 있다면 i+nums[i]까지의 모든 인덱스에도 도달할 수 있습니다. 인덱스 0만 있는 상태에서 시작해 이 구간들을 계속 추가하세요. 새 구간은 이미 확보한 블록 안에서 시작하므로, 도달 가능한 인덱스는 항상 끊기지 않은 하나의 블록, 즉 [0, farthest]를 이룹니다.

그래서 숫자 하나면 충분합니다. i를 왼쪽에서 오른쪽으로 이동하세요. i ≤ farthest인 동안에는 인덱스 i에 도달할 수 있으므로, farthest를 max(farthest, i+nums[i])까지 늘리세요. i가 farthest를 넘어가면, 도달 가능한 어떤 인덱스에서도 i로 점프할 수 없습니다. 이 블록은 그 간격을 넘어 확장될 수 없으므로, 마지막 인덱스를 포함해 그 오른쪽의 어떤 인덱스에도 도달할 수 없습니다. 간격 없이 끝까지 이동하면 마지막 인덱스에 도달할 수 있습니다.

두 번째 예시에서는 farthest가 0에서 시작해 인덱스 0을 지난 뒤 1이 되고, 인덱스 1을 지난 뒤 4가 됩니다. 인덱스 2, 3, 4의 값은 0이므로 farthest는 4에 그대로 있습니다. 인덱스 5는 4를 넘어가므로 답은 false입니다. 첫 번째 예시에서는 인덱스 2가 farthest를 5까지 늘리고, 어떤 인덱스도 이를 넘어가지 않으므로 답은 true입니다.

가장 멀리 도달할 수 있는 위치만 기억해도 안전한 이유는 무엇일까요? 점프를 하나로 확정하지 않기 때문입니다. 이 블록에는 어떤 경로로든 도달할 수 있는 모든 인덱스가 포함되며, 더 가까운 도착 지점은 모두 그 안에 있습니다. 오른쪽 끝을 제외한 나머지를 버려도 정보는 손실되지 않습니다.