[백준 31964번] 반품 회수

문제 링크

https://www.acmicpc.net/problem/31964

(KOI 2024 1차대회 초등부 3번, 고등부 1번)

 

문제 요약

트럭이 직선 도로상의 각 집을 특정 시각 이후에 방문에 물건을 회수한 후 다시 출발지로 돌아올 수 있는 최단 시간을 구하는 문제이다.

 

문제 풀이

그리디로 접근하기

출발지점에서 마지막 집까지 왕복하는 거리인 \(2 \times X_n\)은 트럭이 필수적으로 사용해야 하는 시간이다. 따라서 이 시간을 제외하고 각 집에서 기다려야 하는 시간을 최소화하는 것이 중요하다. 오른쪽 끝 집부터 방문해 물건을 회수하면, 트럭이 출발지점으로 돌아오는 시간에 각 집에서 기다려야 하는 시간이 포함될 수 있다. 그래서 트럭이 가장 오른쪽 집부터 방문에 물건을 회수하는 것이 가장 최선의 선택지이다.

 

시뮬레이션으로 문제 풀기

그리디로 접근해야 한다는 것을 알았으니 시뮬레이션으로 문제를 풀 수 있다. 먼저 \(X_n\)의 시간을 사용해 트럭을 마지막 집으로 이동시키자. 그다음 가장 오른쪽 집부터 왼쪽 집으로 이동하면서 물건을 회수하는 것을 시뮬레이션할 수 있다.

1. 현재 사용한 시간에 \(X_{i+1}\)에서 \(X_{i}\)으로 이동한 시간을 더해준다.
2. 만약 현재 사용한 시간이 \(T_{i}\)보다 크거나 같다면 물건을 회수할 수 있다.
3. 만약 현재 사용한 시간이 \(T_{i}\)보다 작다면 \(T_{i}\)까지 기다린다.

첫 번째 집에서 물건을 회수한 뒤 다시 출발지점으로 돌아오는 것도 시뮬레이션해야 한다는 것을 잊지 말자.

int simulate() {
    int ret = X[n - 1];
    
    for (int i = n - 1 ; i >= 0 ; --i) {
        if (i != n - 1) {
            ret += X[i + 1] - X[i];
        }
        
        if (ret < T[i]) {
            ret = T[i];
        }
    }
    
    ret += X[0];
    
    return ret;
}

 

수식으로 문제 풀기

시뮬레이션으로도 문제를 풀 수 있지만, 수식을 사용하면 조금 더 우아(?)하게 문제를 풀 수 있다. 트럭이 가장 오른쪽 집으로 이동한 뒤, 다시 출발지점으로 쉬지 않고 돌아오는 동안 각 집 \(i\)에 방문하는 시간을 계산해 보자. 이 시간은 \(X_n + (X_n - X_i)\)이다. 이 값이 각 집 \(i\)에서 물건을 내놓는 시간 \(T_i\)보다 작을 수 있어서 각 집에서는 최소 \(Y_i\)만큼의 시간을 기다려야 한다. 이를 수식으로 정리하면 다음과 같다.

$$X_n + (X_n - X_i) + Y_i \geq T_i$$

구해야 하는 값인 \(Y_i\)를 제외하고 전부 오른쪽 항으로 이동해 수식을 정리해보자.

$$Y_i \geq T_i - 2 \times X_n + X_i$$

각 집에 대해 위 수식을 만족하는 가장 작은 \(Y_i\)를 구하고 그 값들 중 가장 큰 \(Y\)를 구한다. 그다음 트럭이 왕복하는 시간 \(2 \times X_n\)에 더해주면 답을 구할 수 있다.

int solve() {
    int Y = 0;
    
    for (int i = 0 ; i < n ; ++i) {
        Y = max(Y, T[i] - 2 * X[n - 1] + X[i]);
    }
    
    return 2 * X[n - 1] + Y;
}