문제 개요
배열 nums와 정수 k가 주어진다고 가정해 봅시다. 우리는 인덱스 0에서 시작하며, 한 번의 이동으로 배열의 경계를 벗어나지 않는 범위 내에서 최대 k칸까지 오른쪽으로 점프할 수 있습니다. 목표는 배열의 마지막 인덱스에 도달하는 것입니다.
점프할 때마다 방문하는 각 인덱스 j에 대해 nums[j] 값이 점수에 누적됩니다. 즉, 최종 점수는 방문한 모든 인덱스의 nums[j] 값의 합입니다. 이때 얻을 수 있는 최대 점수를 구하는 것이 이 문제의 핵심입니다.
예를 들어, 입력이 nums = [1, -2, -5, 7, -6, 4]이고 k = 2라고 가정해 보겠습니다. [1, -2, 7, 4] 순서로 점프하면 1 + (-2) + 7 + 4 = 10으로, 최대 점수인 10을 얻을 수 있습니다.
접근 방식
이 문제는 동적 계획법(DP)과 슬라이딩 윈도우 최댓값 기법을 활용하여 효율적으로 해결할 수 있습니다. 각 인덱스까지 도달했을 때 얻을 수 있는 최대 점수를 scores 배열에 저장하고, 현재 위치에서 도달 가능한 이전 k개 위치 중 최댓값을 활용해 현재 위치의 점수를 계산합니다.
알고리즘 단계
- n := nums의 크기
- scores := 크기가 n이고 0으로 채워진 배열 생성
- scores[0] := nums[0]
- currMax := scores[0]
- max_pt := 0
- n < 1이면 0 반환
- n == 1이면 nums의 마지막 요소 반환
- idx를 1부터 n-1까지 반복:
- max_pt >= idx - k인 경우: currMax가 scores[idx-1]보다 작고 idx > 0이면 currMax와 max_pt를 갱신
- 그렇지 않은 경우(idx - k > 0일 때): currMax를 scores[idx-k]로 초기화한 뒤, idx-k부터 idx-1까지 순회하며 윈도우 내 최댓값과 해당 위치를 다시 계산
- scores[idx] := currMax + nums[idx]
- 반복 종료 후 scores의 마지막 값을 갱신하고 반환
예제 구현
다음 파이썬 코드를 통해 더 잘 이해해 보겠습니다.
def solve(nums, k):
n = len(nums)
scores = [0] * n
scores[0] = nums[0]
currMax = scores[0]
max_pt = 0
if n < 1:
return 0
if n == 1:
return nums[-1]
for idx in range(1, n):
if max_pt >= idx - k:
if currMax < scores[idx-1] and idx > 0:
currMax = scores[idx-1]
max_pt = idx-1
else:
if idx - k > 0:
currMax = scores[idx-k]
max_pt = idx - k
for p in range(idx-k, idx):
if scores[p] >= currMax:
max_pt = p
currMax = scores[p]
scores[idx] = currMax + nums[idx]
scores[-1] = currMax + nums[-1]
return scores[-1]
nums = [1,-2,-5,7,-6,4]
k = 2
print(solve(nums, k))입력
[1,-2,-5,7,-6,4], 2
출력
10
동작 원리
이 알고리즘은 각 인덱스에 대해 직전 k칸 이내의 위치들 중 가장 높은 누적 점수(currMax)를 추적합니다. 현재 최댓값의 위치(max_pt)가 아직 유효한 범위 안에 있다면 새 값과 비교만 하고, 윈도우를 벗어났다면 해당 구간을 다시 순회하며 최댓값을 재계산합니다. 이를 통해 매번 전체를 탐색하지 않고도 각 위치의 최대 점수를 효율적으로 구할 수 있으며, 최종적으로 마지막 인덱스의 점수가 곧 정답이 됩니다.