[백준 31964] 반품 회수 [Python]

문제

아래 그림과 같이 직선 형태의 도로상에 왼쪽부터 오른쪽으로 1번부터 N번까지 번호가 붙어 있는 N개의 집이 있다. i (1 ≤ i ≤ N)번 집의 위치는 X(i)( X(i) > 0 )이다.

 

택배 회사는 한 대의 트럭을 이용해 N개의 집을 방문하면서 반품되는 물건을 회수하려고 한다. 트럭은 택배 회사가 있는 위치 0에서 시각 0에 출발하고, i번 집은 시각 T(i)에 반품할 물건을 내놓는다. 트럭은 1의 속력으로 이동하므로, d만큼의 거리를 이동하는데 d시간이 걸린다. 또한, 트럭은 필요하면 움직이지 않고 제자리에 멈춰서 기다릴 수 있다.

트럭은 반품할 물건이 나와있는 집의 위치를 지나면 순식간에 물건을 회수할 수 있다. 즉, 물건을 회수하는 데 소요되는 시간은 0이다. 따라서 트럭은 위치 X(i)를 시각 T(i) 또는 그 이후에 지나면 i번 집에서 내놓은 물건을 회수할 수 있다.

직선 형태의 도로 위에 있는 집의 위치와 반품할 물건을 내놓는 시각이 주어질 때, 트럭이 모든 물건을 회수해서 다시 택배 회사로 돌아오는 데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하라.

입력

첫 번째 줄에 반품할 물건을 내놓을 집의 개수 N이 주어진다.

두 번째 줄에 각 집의 위치 X1,X2,⋯,XN이 공백으로 구분되어 주어진다.

세 번째 줄에 각 집이 물건을 내놓는 시각 T1,T2,⋯,TN이 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 트럭이 모든 물건을 회수하고 다시 택배 회사로 돌아오기 위해 필요한 시간의 최솟값을 출력한다.

---

풀이

왼쪽에서 출발해 모든 집을 돌며 택배를 수거하고 다시 왼쪽으로 돌아와야 한다.

모든 집이 트럭이 지나가기 전에 물건을 집 밖에 내놓는 문제로 단순화해보자.

트럭은 2X[N] 안에 맨 오른쪽 집까지 방문 후 돌아올 수 있다. 

하지만 현실은 쉽지않다.누군가는 트럭이 지나가기 전에 택배를 내놓지 않을것이다.

그럼 트럭은 제 자리에서 물건을 기달려야 한다.

 

맨 처음 트럭이 맨 우측 집까지 이동하는데 X[N],

물건을 가장 늦게 내놓는 집까지 왼쪽으로 이동하는데 X[N] - X[i],

대기시간까지 합한 시간이 물건을 내놓는 시간인 T[i] 이상임이 성립한다.

T[i] ≤ 2 * X[N] - X[i] + diff

diff = max( T[i] + X[i] - 2 * X[N] )이 성립한다. 이때 대기시간( diff )는 결국 왕복 시간을 포함하고 있다.

왕복시간을 제외한, T[i]와 X[i]의 합만 계산해도 된다.

---

소스코드

보기

---

출처

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