파이썬으로 정확히 k번의 점프로 마지막 섬에 도달하는 방법: 최대 점프 거리의 최솟값 찾기

숫자 배열 A가 주어졌을 때, 배열 A의 i번째 숫자는 i번째 섬의 위치를 나타냅니다. 또 하나의 정수 k(1 ≤ k < N)가 함께 주어집니다. 한 사람이 0번째 섬에 서 있고, 정확히 k번의 점프를 통해 마지막 섬까지 도달해야 한다고 가정해 봅시다. 이때 우리가 구해야 하는 것은 여정 동안 수행하게 되는 점프 중 '가장 긴 점프의 길이'가 최소가 되도록 하는 값입니다. 모든 섬의 위치는 오름차순으로 정렬되어 있다는 점에 유의해야 합니다.

예를 들어 입력이 A = [7, 20, 41, 48], k = 2라고 해보겠습니다. 이 경우 출력은 28이 됩니다. 마지막 섬에 도달할 수 있는 방법은 두 가지입니다. 첫 번째는 7 → 20 → 48 경로인데, 연속된 두 섬 사이의 최대 거리는 20과 48 사이의 28입니다. 두 번째는 7 → 41 → 48 경로인데, 이때 연속된 두 섬 사이의 최대 거리는 7과 41 사이의 34입니다. 따라서 28과 34 중 더 작은 값인 28이 정답이 됩니다.

문제 풀이 접근 방법

이 문제는 이분 탐색(Binary Search)을 활용하면 효율적으로 해결할 수 있습니다. 특정 최대 점프 거리 dist가 주어졌을 때 k번 이내의 점프로 마지막 섬에 도달 가능한지 판단하는 함수를 만들고, dist 값을 이분 탐색으로 조정하며 최적의 최솟값을 찾는 방식입니다.

구체적인 해결 단계는 다음과 같습니다.

isPossible(arr, dist, k) 함수를 정의합니다. 이 함수는 주어진 최대 점프 거리(dist)로 k번 이내의 점프로 끝에 도달할 수 있는지 확인합니다.
n := 배열 arr의 크기
req := 0 (필요한 점프 횟수)
current := 0, previous := 0
i를 0부터 n까지 반복합니다.
- current가 n이 아니고 (arr[current] - arr[previous]) <= dist인 동안 current를 1씩 증가시킵니다.
- req를 1 증가시킵니다(점프 1회 추가).
- current가 n과 같다면 반복문을 종료합니다.
- previous := current - 1로 갱신합니다.
반복 종료 후 current가 n과 같지 않으면 False를 반환합니다(마지막 섬에 도달하지 못함).
req <= k이면 True를 반환하고, 그렇지 않으면 False를 반환합니다.

메인 로직에서는 다음과 같이 진행합니다.

n := 배열 arr의 크기
left := 0, right := 배열의 마지막 원소
ans := 0
left <= right인 동안 반복합니다.
- mid := (left + right) // 2
- isPossible(arr, mid, k)가 참이라면 ans := mid로 저장하고, 더 작은 값도 가능한지 확인하기 위해 right := mid - 1로 설정합니다.
- 그렇지 않다면 left := mid + 1로 설정하여 더 큰 거리를 탐색합니다.
탐색이 끝나면 ans를 반환합니다.

예제 코드

아래 파이썬 구현 예제를 통해 더 잘 이해해 보겠습니다.

def isPossible(arr, dist, k):
    n = len(arr)
    req = 0
    current = 0
    previous = 0
    for i in range(0, n):
        while (current != n and (arr[current] - arr[previous]) <= dist):
            current += 1
        req += 1
        if (current == n):
            break
        previous = current - 1
    if (current != n):
        return False
    if (req <= k):
        return True
    return False

def minimum_distance(arr, k):
    n = len(arr)
    left = 0
    right = arr[-1]
    ans = 0
    while (left <= right):
        mid = (left + right) // 2
        if (isPossible(arr, mid, k)):
            ans = mid
            right = mid - 1
        else:
            left = mid + 1
    return ans

arr = [7, 20, 41, 48]
k = 2
print(minimum_distance(arr, k))

입력

[7, 20, 41, 48] , 2

출력

정리

이 알고리즘의 시간 복잡도는 O(N log D)입니다. 여기서 N은 섬의 개수, D는 마지막 섬의 좌표 값입니다. isPossible 함수는 배열을 한 번 순회하며 필요한 점프 횟수를 계산하고(O(N)), 이분 탐색은 log(D)번 반복되기 때문입니다. 이처럼 이분 탐색과 탐욕적(Greedy) 검증 로직을 결합하면, 제한된 점프 횟수 안에서 최대 점프 거리를 최소화하는 문제를 효율적으로 해결할 수 있습니다.