각 숫자가 해당 위치에서 최대로 점프할 수 있는 거리를 나타내는 숫자 리스트 nums가 주어졌다고 가정해 보겠습니다. 이때 인덱스 0에서 시작하여 마지막 인덱스에 도달할 수 있는지 판별하는 프로그램을 작성해야 합니다.
예를 들어, 입력이 nums = [2,5,0,2,0]이라면 결과는 True입니다. 인덱스 0에서 인덱스 1로 점프한 뒤, 인덱스 1의 값이 5이므로 마지막 위치까지 한 번에 점프할 수 있기 때문입니다.
해결 접근 방식
이 문제는 동적 계획법(DP)을 이용해 배열의 끝에서부터 앞으로 거슬러 올라가며 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
n:= nums의 길이arr:= 크기가 n인 배열을 생성하고 모든 값을 False로 초기화arr[n - 1]:= True (마지막 인덱스는 항상 도달 가능)- i를 n-2부터 0까지 1씩 감소시키면서 반복:
arr[i]:= i+1부터 i + nums[i]까지 범위의 arr 값 중 하나라도 True이면 True로 설정
- 최종적으로
arr[0]을 반환
즉, 각 위치에서 그 위치의 점프 거리 안에 도달 가능한 지점이 존재하는지 확인하면 됩니다. 시간 복잡도는 최악의 경우 O(n²)이며, 공간 복잡도는 O(n)입니다.
예제 코드
class Solution:
def solve(self, nums):
n = len(nums)
arr = [False] * n
arr[n - 1] = True
for i in range(n - 2, -1, -1):
arr[i] = any(arr[i + 1 : i + nums[i] + 1])
return arr[0]
ob = Solution()
nums = [2,5,0,2,0]
print(ob.solve(nums))
입력
[2,5,0,2,0]
출력
True
이처럼 뒤에서부터 도달 가능 여부를 누적적으로 계산하면, 시작점(인덱스 0)에서 마지막 인덱스에 도달할 수 있는지 효율적으로 판별할 수 있습니다.