문제 69
제한된 점프
$1$번부터 $N$번까지 번호가 붙은 칸이 있다. 처음에는 $1$번 칸에 있으며 한 번에 오른쪽으로 $1$칸 이상 $K$칸 이하 이동할 수 있다.
$i$번 칸에 도착할 때 비용 $A_i$를 내야 한다. $1$번 칸의 비용도 낸다고 할 때 $N$번 칸에 도착하는 데 필요한 비용의 최솟값을 출력하라.
입력
첫 번째 줄에 두 정수 $N$, $K$가 공백으로 구분되어 주어진다. $(2 \le N \le 5 \cdot 10^6; 1 \le K < N)$
두 번째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(-10^9 \le A_i \le 10^9)$
출력
첫 번째 줄에 $1$번 칸에서 $N$번 칸까지 이동하는 데 필요한 비용의 최솟값을 출력한다.
예제 입력 1
7 3 4 2 7 -3 5 1 6
예제 출력 1
7
공식 해설
$N$이 최대 $5\cdot10^6$이므로 이전 $K$개 위치를 매번 모두 보는 $O(NK)$ 전이는 피해야 한다. 이동할 수 있는 이전 위치들이 연속 구간이라는 점을 이용한다.
$i$번 칸에 도착하는 최소 비용을 $D_i$라 하자. 시작 칸의 비용도 내므로 $D_1=A_1$이고, 나머지는 마지막 점프의 출발점을 골라
\[
D_i=A_i+\min_{\max(1,i-K)\le j<i}D_j
\]
로 계산한다.
필요한 것은 최근 $K$개 상태의 최솟값이다. 인덱스가 증가하고 $D$ 값도 증가하도록 후보를 단조 덱에 저장한다.
$i$를 계산하기 전에 앞에서 $j<i-K$인 후보들을 제거한다. 이제 덱의 맨 앞 값에 $A_i$를 더하면 $D_i$이다. 새 후보를 넣기 전에는 뒤에서 $D_j\ge D_i$인 후보들을 제거한다. 새 후보 $i$는 비용이 더 크지 않고 유효 범위에 더 오래 남으므로, 이후 어느 시점에도 제거한 후보보다 불리하지 않다.
각 상태가 덱에 한 번 들어가고 최대 한 번 나오므로 시간복잡도는 $O(N)$이다. 입력을 읽으며 인덱스와 비용만 덱에 저장하면 공간복잡도는 $O(K)$이다. 마지막에 구한 $D_N$을 출력한다. 누적 비용의 절댓값은 $N\cdot10^9$ 이하이다.
구현 · 언어별 풀이
C++ 구현
deque<pair<int, long long>>에 인덱스와 비용을 함께 저장한다. 첫 상태 $(1,A_1)$을 넣고 나머지를 순서대로 계산한다. 범위를 벗어난 후보는 앞에서, 새 후보에 밀리는 값은 뒤에서 제거한다. 입력을 읽는 즉시 처리하면 전체 비용 배열은 필요 없다.
C 구현
입력값을 하나씩 읽고 인덱스·long long dp의 단조 덱만 둔다. 원형 배열 크기는 $K+1$로 잡을 수 있다. 범위를 벗어난 앞 원소와 새 dp 이상인 뒤 원소를 제거한 뒤 현재 상태를 넣는다.
Python 구현
dp 전체와 전체 split 토큰을 동시에 저장하지 않는다. 인덱스와 dp를 고정 크기 자료형의 원형 배열에 저장하면 큰 $K$에서 튜플 객체 비용을 줄인다. 입력을 청크로 읽고 범위 만료·뒤쪽 지배 상태 제거를 각각 처리한다.
Java 구현
최대 $5\cdot10^6$개의 상태에 각각 객체를 만들지 않고 int[] 인덱스와 long[] dp의 원형 덱을 둔다. BufferedInputStream으로 입력을 순차 처리한다. 현재 dp만 계산하고 앞선 범위 밖 상태는 버린다.
Rust 구현
VecDeque<(usize,i64)>로 단조 큐를 유지한다. 입력을 순차 파싱하고 전체 dp 배열은 만들지 않는다. 새 dp 이상인 뒤 상태를 pop_back하고 오래된 상태를 pop_front한다.
JavaScript 구현
DP 합의 절댓값은 $N\cdot10^9\le5\cdot10^{15}$이므로 Number로 정확하게 저장할 수 있다. 다만 $32$비트에는 들어가지 않으므로 덱의 DP 값은 Float64Array에, 위치는 Int32Array에 둔다.
앞·뒤 인덱스가 있는 길이 $K+1$의 원형 덱으로 공통 풀이의 후보 제거와 삽입을 처리한다. 최대 $5\cdot10^6$개의 입력값은 fs.readSync의 고정 크기 Buffer에서 순서대로 읽으면 전체 토큰·DP 배열 없이 $O(K)$의 작업 메모리를 유지할 수 있다.