# Jump Game

class Solution:
    def canJump(self, nums: list[int]) -> bool:
        answer = True
        max_idx = 0
        now_idx = 0
        if max_idx >= len(nums)-1:
            return answer
        while now_idx < len(nums) - 1 and now_idx <= max_idx:
            max_idx = max(max_idx, now_idx + nums[now_idx])
            if max_idx >= len(nums)-1:
                break
            now_idx += 1
        else:
            answer = False
        
        return answer


"""
걸린 시간: 40분

복잡도: while문이지만 많아도 now_idx가 nums를 한번씩 다 확인하면 끝나기 때문에 시간복잡도는 O(n)이다.
변수 3개만 활용하기 때문에 공간복잡도는 O(1)이다.

해설: i번째에서 포함할 수 있는 미래의 좌표 최대값(max_idx)을 기록해둔 후, 그 최대값이 최종 인덱스를 넘는지 확인하면된다.
순회는 순서대로 하나의 인덱스씩 진행하며, 만약 max_idx를 현재 보는 인덱스가 초과했다면 미래 좌표의 범위가 끊겼다는 이야기이므로
그 좌표까지 도달하지 못한다는 말이므로 반복을 끝내고 False를 출력한다.
nums의 전체 길이가 1인 경우에는 반복문이 시작하자마자 끝나서 answer가 False가 되므로 예외처리 한다.

이 예외처리 때문에 과거에 풀었던 풀이가 훨씬 낫다. -> 거꾸로 오면서 최종 인덱스에 도달할 수 있는 이전 인덱스를 갱신하는데 이게 0이 되면 True
"""