[BOJ 11475] Journey to the "The World's Start"

체감 난이도: Platinum IV - 0.3

 

태그

• Binary Search (이진 탐색) & Parametric Search (매개 변수 탐색)
• Dynamic Programming (동적 계획법)
• Sliding Window (슬라이딩 윈도우)
• Set / Multiset

 

풀이

1. 최대 \( r \)미터를 이동하기 위한 티켓의 가격을 재정비해보자.

\( r \)미터를 이동하기 위한 티켓의 가격은 이미 문제에서 \( p_r \)로 주어집니다.

 

하지만, 만약 \( r' > r \)이면서 \( p_r' < p_r \)인 \( r' \)이 존재한다면?

즉, 범위는 더 넓은데 가격이 더 싼 게 존재한다면?

\( r \)미터까지만 이동한다 하더라도 \( r' \)에 대한 티켓을 사는 것이 가격 상 이득이 됩니다.

 

그러니 최대 \( r \)미터를 이동하기 위한 티켓의 가격 \( p_r \)을, \( \min(p_r, p_{r+1}, \ldots, p_{N-1}) \)로 바꿔볼 수 있습니다.

 

2. 재정비한 비용을 토대로, 무엇을 생각해볼 수 있을까?

우선, \( r_1 < r_2 \)라면 \( p_{r_1} \le p_{r_2} \)임이 보장됩니다.

즉, 더 먼 거리를 이동하기 위해서는 더 많은 돈을 내야 하는 거죠.

 

또한, \( t_{r} \)을 최대 \( r \)미터까지 이동할 수 있을 때 \( 1 \)번에서 \( N \)번 역까지 가는 데 필요한 최소 시간이라고 하면, 자명하게 \( r_1 < r_2 \)라면 \( t_{r_1} \le t_{r_2} \)입니다. (\( r_1 \)에서 하는 짓을 \( r_2 \)에서 똑같이 해줄 수 있으므로)

 

이는, 최대 이동 거리 \( r \)과 가격 \( p_{r} \), 그리고 최소 시간 \( t_{r} \)이 모두 증가함수임을 알려줍니다.

그렇다면, \( t \)초 안에 도착할 수 있는 최소 가격 \( p_{r} \)을, \( t_{r} le t \)인 최대 \( r \)로 찾을 수 있다는 것을 의미합니다.

 

간단히 말하자면, \( r \)로 매개 변수 탐색 + 이진 탐색을 진행해줄 수 있습니다.

 

\( r \)로 매개 변수 탐색을 진행하므로, 이 밑에서는 최대 이동 거리 \( r \)이 고정되어있다고 가정하겠습니다.

 

3. 과연 뒤로 가는 게 이득일까?

그렇다고 가정해봅시다.

즉, 최적인 경로가 \( 1 \Rightarrow p \rightarrow q \Rightarrow N \)이고, 이 때 \( p > q \)라고 합시다.

다르게 말하자면, 우리의 경로는 \( p \)에서 \( q \)로 뒤로 가는 걸 포함하는 경로입니다.

증명을 위해, 이러한 \( (p, q) \) 쌍이 여러 개 존재한다면 그 중 맨 뒤에 있는 걸 고르겠습니다.

 

만약 이게 가능했다면, \( 1 \Rightarrow p \Rightarrow N \)으로 가는 게 시간이 덜 걸리게 됩니다.

 

\( q \)에서 \( N \)까지 가는 경로는 우리가 선택한 \( (p, q) \)의 특성상 항상 올라가게 됩니다.

그런데 항상 올라가게 된다는 것은, 어느 순간 \( p \)를 다시 지나가게 된다는 것이고,

이는 \( p \)에서 출발하는, 더 짧은 경로를 만들 수 있음을 의미합니다.

그림 요약. 빨간 경로 대신 파란 경로가 직관적으로만 봐도 더 빠르다. 실제로도 이동 거리와 쉬는 시간 둘 다 줄어듦을 볼 수 있다.

 

이제 이걸 잘 적용해주면, 최적의 경로는 그냥 앞으로만 가는 것임을 알 수 있습니다.

이는 중요한 사실인데, 우선 이동 거리가 \( N-1 \)로 고정되므로 역에서 쉬는 시간만 고려하면 되고

\( i \)번 역까지 가는 데 걸리는 시간은 \( 1 \)번부터 \( i-1 \)번 역까지만 고려해도 되기 때문입니다.

 

4. 이동 가능한 최대 거리 \( r \)이 고정될 때, 도착점까지 가는 데 걸리는 최소 시간은?

(3번)에 의해, \( i \)번 역까지 가는 데 걸리는 시간은 \( 1 \)번부터 \( i-1 \)번 역까지만 고려해서 구할 수 있습니다.

그러니, \( D_{i} = \) \( i \)번 역까지 오는 데 걸리는 최소 시간 을 정의해봅시다.

 

초항은 간단합니다. \( D_{1} = 0 \)이죠.

점화식은... 자세히 생각해봅시다.

 

최대 이동 거리가 \( r \)이므로, \( i \)번 역에 오기 위해서는 \( j (\ge i-r) \)번 역에서 \( i \)번 역으로 와야 합니다.

그 뒤로는, \( i \)번 역에서 갈아타는 데 걸리는 시간 \( d_{i} \)를 더해줘야죠.

즉, \( D_{i} = \min\limits_{i-r \le j < i}(D_{j}) + d_{i} \)가 됩니다.

 

하지만 이 점화식을 \( D_{N} \)까지 계산하려면 \( O(Nr) \)의 시간이 걸리게 됩니다.

\( r \)로 매개 변수 탐색 + 이진 탐색을 돌릴 걸 고려하면, \( O(N^2 \log N) \)이죠.

 

하지만 \( D_{i} \)의 점화식이 어딘가 수상합니다.

\( D_{i} \)을 구하기 위해서는, 크기가 \( r \)인 구간에서의 \( D_{j} \)의 최솟값을 알고 있으면 됩니다.

이는 Sliding Window처럼, \( D_{i} \)를 넣고 \( D_{i-r} \)을 빼가면서 \( \min(D_{j}) \)를 관리해주면 됩니다.

 

이렇게 하면 \( O(N \log N) \)의 시간에 \( D_{N} \)까지 구할 수 있고,

최종 시간 복잡도는 \( O(N \log^2 N) \)이 됩니다.

 

코드

ll arr[50020], val[50020];
ll dp[50020];
 
void Main(){
    int n; ll t; cin >> n >> t; t -= n-1;
    for (int i = 1; i < n; i++){ cin >> val[i]; }
    for (int i = 2; i < n; i++){ cin >> arr[i]; }
    for (int i = n-2; i >= 1; i--){ val[i] = min(val[i], val[i+1]); }
    int st = 1, ed = n-1, ans = n-1; while (st <= ed){
        int mid = st+ed >> 1;
        memset(dp, 0, sizeof(dp));
        multiset<ll> s; s.insert(dp[1]);
        for (int i = 2; i <= n; i++){
            int j = i-mid;
            dp[i] = *(s.begin()) + arr[i]; s.insert(dp[i]);
            if (j >= 1){ s.erase(s.find(dp[j])); }
        }
        if (dp[n] <= t){ ans = mid; ed = mid-1; } else{ st = mid+1; }
    }
    cout << val[ans];
}