정확히 K번 점프해 모을 수 있는 최대 점수

자바스크립트 코딩테스트 문제로 binary-lifting 주제를 연습해보세요. 난이도는 hard이며, 브라우저에서 바로 JavaScript로 풀이를 실행할 수 있습니다.

today hard binary-lifting 함수명: solution 제한 시간: 400ms

텔레포터 구역이 0번부터 n - 1번까지 있고, 각 구역 i에서는 다음 점프에서 반드시 next[i]로 이동합니다.

또한 각 구역에는 점수 scores[i]가 적혀 있습니다. 어떤 구역에 점프해서 착지할 때마다 그 구역의 점수를 얻거나 잃습니다.

시작할 때는 원하는 아무 구역에서나 출발할 수 있지만, 출발한 순간에는 점수를 얻지 않습니다. 점수는 오직 점프 후 착지한 칸에서만 반영됩니다.

정확히 k번 점프해야 할 때, 만들 수 있는 최대 총점을 반환하세요.

제한사항

1 <= next.length === scores.length <= 200000
0 <= next[i] < n
-1000000 <= scores[i] <= 1000000
1 <= k <= 1000000000000
각 구역에서는 다음 이동지가 하나로 고정되어 있습니다.
시작 구역은 자유롭게 선택할 수 있습니다.
점수는 출발 시에는 얻지 않고, 각 점프의 착지 구역 점수만 누적합니다.
반환값은 JavaScript의 안전한 정수 범위를 넘지 않는다고 가정합니다.

예시

입력: next = [1, 2, 0], scores = [5, -2, 4], k = 4 → 출력: 12
- 2에서 시작하면 착지 순서는 0 -> 1 -> 2 -> 0이고 점수 합은 5 + (-2) + 4 + 5 = 12입니다.
입력: next = [0, 0, 0], scores = [7, -3, 2], k = 5 → 출력: 35
- 0에서 시작하면 매번 다시 0에 착지하므로 7을 5번 얻어 35가 됩니다.
입력: next = [1, 2, 0, 2], scores = [3, 9, -4, 8], k = 4 → 출력: 17
- 0에서 시작하면 착지 순서는 1 -> 2 -> 0 -> 1이고 점수 합은 9 + (-4) + 3 + 9 = 17입니다.

힌트

k가 최대 10^12라서 시작점마다 한 칸씩 직접 시뮬레이션하면 불가능합니다.
2^0, 2^1, 2^2, … 번 점프했을 때의 정보를 미리 합쳐 두면 큰 점프 수를 빠르게 분해할 수 있습니다.
단순히 다음 위치만 저장하지 말고, 그 점프 묶음 동안 얻는 점수 합도 함께 저장해야 합니다.

해설

이 문제의 그래프는 각 정점에서 나가는 간선이 정확히 하나인 functional graph입니다.

직접 시뮬레이션하면 어떤 시작점 s에 대해서도 k번 이동하는 데 O(k)가 걸립니다. 하지만 k는 최대 10^12이므로 불가능합니다.

핵심은 점프 횟수를 2의 거듭제곱 단위로 미리 묶어 두는 것입니다.

1. doubling 테이블 정의

다음 두 배열을 생각합니다.

up[p][i]: i에서 시작해 정확히 2^p번 점프했을 때의 도착 구역
sum[p][i]: i에서 시작해 정확히 2^p번 점프하는 동안 착지해서 얻는 점수 합

가장 작은 단계는 바로 만들 수 있습니다.

up[0][i] = next[i]
sum[0][i] = scores[next[i]]

왜냐하면 1번 점프하면 next[i]에 도착하고, 그때 얻는 점수는 그 칸의 점수이기 때문입니다.

2. 점화식으로 큰 점프 만들기

2^p번 점프는 2^(p-1)번 점프를 두 번 이어 붙인 것과 같습니다.

먼저 i에서 2^(p-1)번 점프해 mid = up[p - 1][i]에 도착하고, 다시 거기서 2^(p-1)번 더 점프합니다.

따라서

up[p][i] = up[p - 1][ up[p - 1][i] ]
sum[p][i] = sum[p - 1][i] + sum[p - 1][ up[p - 1][i] ]

이렇게 하면 모든 p와 i에 대한 정보를 O(n log k)에 준비할 수 있습니다.

3. 각 시작점의 정확한 k번 점프 점수 계산

이제 k를 이진수로 보면서 켜진 비트만 따라가면 됩니다.

예를 들어 k = 13이면 13 = 8 + 4 + 1이므로,

2^3번 점프 정보
2^2번 점프 정보
2^0번 점프 정보 를 순서대로 적용하면 됩니다.

각 시작점마다:

현재 위치를 시작점으로 둡니다.
k의 각 비트를 보며 켜진 비트 p가 있으면
- answer += sum[p][current]
- current = up[p][current]
이렇게 얻은 총점으로 최댓값을 갱신합니다.

4. 왜 이 풀이가 맞는가?

sum[p][i]는 정확히 2^p번 점프 구간의 점수 합을 담고 있고, up[p][i]는 그 구간이 끝난 뒤의 위치를 담고 있습니다.

따라서 k를 이진수로 분해해 해당 구간들을 차례대로 붙이면,

이동 순서가 정확히 보존되고
각 구간의 점수 합도 빠짐없이 한 번씩만 더해집니다.

즉, 실제로 k번 점프한 결과와 완전히 같은 값을 얻습니다.

5. 복잡도

테이블 구성: O(n log k)
모든 시작점 평가: O(n log k)
전체: O(n log k)

n <= 200000, k <= 10^12이면 log2(k)는 약 40 정도라 충분히 가능합니다.

구현 팁

JavaScript에서는 k가 매우 클 수 있으므로 BigInt를 사용하는 편이 안전합니다. 비트를 확인할 때도 1n, 2n처럼 BigInt 리터럴을 써서 처리하면 큰 k를 정확하게 다룰 수 있습니다.

코드 작성

starter code를 바탕으로 함수를 완성한 뒤 예제 테스트를 실행해보세요.

JavaScript 에디터 로딩 중...

커스텀 테스트

함수 인자를 JSON 배열 형태로 입력하세요. 예: [3, 5], [[1, 2, 3]]

아직 실행하지 않았습니다.

실행 결과

아직 실행하지 않았습니다.

예제 테스트를 실행하면 여기에서 결과를 확인할 수 있습니다.

댓글

문제 풀이 아이디어, 질문, 반례를 자유롭게 나눠보세요.