문제 개요
정수 배열 arr와 정수 d가 주어집니다. 한 번의 이동으로 인덱스 i에서 아래 두 가지 방식으로 점프할 수 있습니다.
- i + x : 단, i + x < n 이고 x는 1부터 d 사이의 값
- i - x : 단, i - x >= 0 이고 x는 1부터 d 사이의 값
여기서 n은 배열의 크기입니다. 추가로, 인덱스 i에서 인덱스 j로 점프하려면 arr[i] > arr[j]를 만족해야 하며, i와 j 사이에 있는 모든 인덱스 k에 대해서도 arr[i] > arr[k] 조건을 충족해야 합니다. 우리는 배열의 어떤 인덱스든 자유롭게 선택해 점프를 시작할 수 있고, 방문할 수 있는 최대 인덱스 개수를 구해야 합니다.
예시로 이해하기
예를 들어 d = 2이고 높이 배열이 다음과 같다고 가정해 보겠습니다.
이 경우 출력값은 4입니다. 인덱스 10에서 시작하여 10 → 8 → 6 → 7 순서로 점프할 수 있기 때문입니다.
반면 인덱스 6에서 시작하면 인덱스 7로만 점프할 수 있습니다. arr[5] = 13이 arr[6] = 9보다 크기 때문에 인덱스 5로는 점프할 수 없고, 인덱스 4와 6 사이에 인덱스 5가 끼어 있어 역시 인덱스 4로도 이동할 수 없습니다. 마찬가지로 인덱스 3에서 인덱스 2나 인덱스 1로 점프하는 것도 불가능합니다.
해결 전략: 메모이제이션 기반 DFS
이 문제는 각 인덱스에서 시작했을 때 방문할 수 있는 최대 칸 수를 계산한 뒤, 그중 최댓값을 찾는 방식으로 해결할 수 있습니다. 동일한 인덱스에 대한 계산이 반복되지 않도록 메모이제이션(DP 배열)을 활용합니다.
알고리즘 단계
- 결과를 저장할 dp 배열을 정의합니다.
- solve(arr, idx, d) 함수를 정의합니다.
- dp[idx]가 -1이 아니라면 이미 계산된 값이므로 dp[idx]를 그대로 반환합니다.
- ret := 1 로 초기화하고, n := 배열의 크기로 설정합니다.
- i = idx + 1 부터 오른쪽 방향으로 탐색합니다.
- i > idx + d 이면 반복을 종료합니다. (점프 거리 초과)
- arr[i] >= arr[idx] 이면 반복을 종료합니다. (더 높거나 같은 지점은 통과 불가)
- ret := max(ret, 1 + solve(arr, i, d)) 로 최댓값을 갱신합니다.
- i = idx - 1 부터 왼쪽 방향으로 동일하게 탐색합니다.
- i < idx - d 이면 반복을 종료합니다.
- arr[i] >= arr[idx] 이면 반복을 종료합니다.
- ret := max(ret, 1 + solve(arr, i, d)) 로 최댓값을 갱신합니다.
- dp[idx] := ret 을 저장한 후 ret을 반환합니다.
- 메인 함수에서는 모든 인덱스를 시작점으로 삼아 solve()를 호출하고, 그 결과의 최댓값을 반환합니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> dp;
int solve(vector <int>& arr, int idx, int d){
if (dp[idx] != -1)
return dp[idx];
int ret = 1;
int n = arr.size();
for (int i = idx + 1; i < n; i++) {
if (i > idx + d)
break;
if (arr[i] >= arr[idx])
break;
ret = max(ret, 1 + solve(arr, i, d));
}
for (int i = idx - 1; i >= 0; i--) {
if (i < idx - d)
break;
if (arr[i] >= arr[idx])
break;
ret = max(ret, 1 + solve(arr, i, d));
}
return dp[idx] = ret;
}
int maxJumps(vector<int>& arr, int d) {
int n = arr.size();
dp = vector<int>(n, -1);
int ret = 1;
for (int i = 0; i < n; i++) {
ret = max(ret, solve(arr, i, d));
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {6,4,14,6,8,13,9,7,10,6,12};
cout << (ob.maxJumps(v, 2));
}입력
{6,4,14,6,8,13,9,7,10,6,12}, 2출력
4
마무리
이 알고리즘은 각 인덱스마다 최대 d칸씩 좌우로 탐색하므로 시간 복잡도는 O(n × d)입니다. 메모이제이션 덕분에 같은 인덱스에 대한 중복 계산이 제거되어 효율적으로 동작하며, 배열의 모든 위치를 출발점으로 고려해 전체 최적해를 보장합니다.