최소 점프 수 문제 – 동적 계획법(DP) 풀이와 C++ 구현

문제 개요

이 문제에서는 양의 정수로 이루어진 리스트가 주어집니다. 각 정수는 현재 위치에서 최대 이동할 수 있는 칸 수를 의미합니다. 첫 번째 원소에서 출발하여 리스트의 마지막 원소에 도달할 때까지 필요한 최소 점프 횟수를 구하는 것이 목표입니다.

동적 계획법(DP) 접근 방식

동적 계획법으로 해결할 때는 최소 점프 횟수를 저장하기 위한 jumps 배열을 정의합니다. 여기서 jumps[i]는 0번 인덱스에서 i번 인덱스까지 도달하는 데 필요한 최소 점프 횟수를 나타냅니다.

입력 및 출력 예시

입력:
정수 리스트 {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9}

출력:
마지막 위치에 도달하기 위한 최소 점프 횟수: 3

풀이 과정:
값 1에서 시작하여 값 3으로 이동하고,
3칸을 점프하여 값 8에 도달한 뒤,
다시 점프하여 마지막 원소에 도달합니다.

알고리즘

함수: minPossibleJump(list, n)

입력: 숫자 배열, 배열의 원소 개수 n

출력: 끝에 도달하기 위해 필요한 최소 점프 횟수

Begin
    크기가 n인 배열 jump를 정의한다
    if n = 0 또는 list[0] = 0 이면
        return ∞
    jump[0] := 0

    for i := 1 to n-1, do
        jumps[i] := ∞
        for j := 0 to i-1, do
            if i <= j + list[j] 그리고 jump[j] ≠ ∞ 이면
                jump[i] := jump[i]와 (jump[j] + 1) 중 최솟값
                반복문 탈출
        done
    done

    return jump[n-1]
End

C++ 구현 예제

#include<iostream>
using namespace std;

int min(int x, int y) {
    return (x < y)? x: y;
}

int minPossibleJump(int list[], int n) {
    int *jumps = new int[n];      // 점프 횟수를 저장할 배열을 동적으로 생성
    if (n == 0 || list[0] == 0)
        return INT_MAX;
    jumps[0] = 0;

    for (int i = 1; i < n; i++) {
        jumps[i] = INT_MAX;       // 초기값을 무한대(INT_MAX)로 설정
        for (int j = 0; j < i; j++) {
            if (i <= j + list[j] && jumps[j] != INT_MAX) {
                jumps[i] = min(jumps[i], jumps[j] + 1);
                break;
            }
        }
    }
    return jumps[n-1];
}

int main() {
    int list[] = {1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9};
    int size = 11;
    cout << "끝에 도달하기 위한 최소 점프 횟수: " << minPossibleJump(list,size);
    return 0;
}

실행 결과

끝에 도달하기 위한 최소 점프 횟수: 3

복잡도 분석

이 알고리즘은 각 인덱스 i에 대해 그 이전의 모든 인덱스 j를 검사하므로 시간 복잡도는 O(n²)입니다. 추가로 사용되는 jumps 배열 때문에 공간 복잡도는 O(n)입니다.

참고로, 입력 배열의 첫 번째 값이 0이면 어디로도 이동할 수 없으므로 끝에 도달하는 것이 불가능하며, 이 경우 무한대(INT_MAX)를 반환하여 도달 불가능함을 나타냅니다.