양의 정수로 구성된 배열이 주어졌을 때, 각 요소는 해당 인덱스에서 한 번에 점프할 수 있는 최대 칸 수를 의미합니다. 이 문제의 목표는 각 요소에서 출발하여 배열의 끝에 도달할 수 있는 서로 다른 점프 경로의 수를 구하는 것입니다.
예를 들어 arr[] = [1, 2, 3]인 경우를 살펴보겠습니다. 값이 1인 요소는 1칸만 점프할 수 있고, 값이 2인 요소는 1칸 또는 2칸을, 값이 3인 요소는 1칸, 2칸, 3칸 중 원하는 만큼 점프할 수 있습니다.
예제 1
입력
arr[] = {1, 2, 3}출력
배열 끝에 도달하는 점프 방법의 수: 1 1 0
설명
- 요소 1: 1칸 점프 가능 → 정확히 1번의 점프로 끝에 도달 → 방법 1가지
- 요소 2: 1칸 또는 2칸 점프 가능 → 끝에 도달하려면 1칸 점프 한 번이면 충분 → 방법 1가지
- 요소 3: 1~3칸 점프 가능하지만 이미 마지막 요소이므로 추가 점프가 필요 없음 → 0
예제 2
입력
arr[] = {4, 3, 6, 2}출력
배열 끝에 도달하는 점프 방법의 수: 4 2 1 0
설명
- 요소 4: 1~4칸 점프 가능. 끝에 도달하는 경로는 4→3→6→2, 4→6→2, 4→2, 4→3→2로 총 4가지
- 요소 3: 1~3칸 점프 가능. 경로는 3→6→2, 3→2로 총 2가지
- 요소 6: 1~5칸 점프 가능하지만 끝까지는 1칸이면 충분. 경로는 6→2로 총 1가지
- 요소 2: 이미 마지막 요소이므로 점프가 필요 없음 → 0
해결 접근 방식
이 문제는 뒤에서부터 앞으로 순회하는 동적 프로그래밍(DP) 기법으로 효율적으로 해결할 수 있습니다. 각 요소 arr[i]에 대해, 현재 위치에서 도달 가능한 뒤쪽 요소들이 가진 "끝 도달 방법의 수"를 모두 더하고, 한 번의 점프로 끝에 직접 도달할 수 있는 경우도 1가지로 세어줍니다.
- 정수 배열 arr[]를 입력으로 받습니다.
- reach_end(int arr[], int size) 함수는 배열과 크기를 받아 각 요소별 끝 도달 방법의 수를 계산합니다.
- 결과를 저장할 별도의 배열 arr_2[]를 준비하고 memset()으로 0으로 초기화합니다.
- 마지막 요소는 제외하므로 for 루프를 i = size-2부터 i = 0까지 역순으로 순회합니다.
- temp = size - i - 1을 계산합니다. temp ≤ arr[i]라면 한 번의 점프로 끝에 직접 도달할 수 있으므로 arr_2[i]++ 합니다.
- j = i+1부터 j < size-1 && j ≤ arr[i]+i 범위의 요소들을 확인하여, arr_2[j]가 -1(끝 도달 불가)이 아닌 경우 해당 값을 arr_2[i]에 더해줍니다.
- 모든 계산 후에도 arr_2[i]가 0이라면 끝에 도달할 수 없다는 의미로 -1로 설정합니다.
- 모든 순회가 끝나면 arr_2[]에는 각 요소별 끝 도달 방법의 수가 저장되며, 이를 출력합니다.
C++ 코드 예제
#include <bits/stdc++.h>
using namespace std;
void reach_end(int arr[], int size){
int arr_2[size];
memset(arr_2, 0, sizeof(arr_2));
for (int i = size-2; i >= 0; i--){
int temp = size - i - 1;
if (arr[i] >= temp){
arr_2[i]++;
}
for (int j = i+1; j < size-1 && j <= arr[i] + i; j++){
if (arr_2[j] != -1){
arr_2[i] = arr_2[i] + arr_2[j];
}
}
if(arr_2[i] == 0){
arr_2[i] = -1;
}
}
cout<<"배열 끝에 도달하는 점프 방법의 수: ";
for (int i=0; i < size; i++){
cout<<arr_2[i] << " ";
}
}
int main(){
int arr[] = {2, 3, 7, 1, 8, 9};
int size = sizeof(arr) / sizeof(arr[0]);
reach_end(arr, size);
return 0;
}출력 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
배열 끝에 도달하는 점프 방법의 수: 8 5 3 1 1 0
복잡도 분석
각 요소마다 최대 arr[i]개의 뒤쪽 요소를 확인해야 하므로 시간 복잡도는 O(n²)입니다. 공간 복잡도는 결과를 저장하는 보조 배열 하나만 사용하므로 O(n)입니다.