[백준 31964] 반품 회수 (C++)

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

문제

---

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

 

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

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

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

 

입력

---

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

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

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

 

출력

---

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

제한

---

• 주어지는 모든 수는 정수이다.
•  1 ≤ N ≤ 3000
•  1 ≤ X1 < X2 < ⋯ < XN≤108
•  0 ≤ Ti ≤ 108 (1 ≤ i ≤ N)

서브태스크

---

번호	배점	제한
1	10	N=2
2	15	N ≤ 9
3	5	모든 1 ≤ i ≤ N에 대해 Ti = 0
4	25	모든 2 ≤ i ≤ N에 대해 Ti−1 ≤ Ti
5	45	추가 제약 조건 없음

 

문제 풀이

---

그리디 문제.

 

트럭이 모든 집을 한 번은 거쳐서 다시 시작 지점인 0으로 돌아와야 한다. 따라서 다른 집에 먼저 택배를 픽업하는 것보다 맨 마지막 집에 처음으로 픽업하러 가는 것이 가장 빠르다.  픽업 자체에 드는 시간은 없으므로 맨 마지막 집으로 이동하면서 픽업할 수 있는 집이 있다면 픽업해도 좋다.

맨 마지막 집까지 이동하여 픽업까지 드는 시간은 맨 마지막 집까지의 거리와 맨 마지막 집이 택배를 반품하는 시간을 비교하여 둘 중 큰 값이다. 이제 0번째 집까지 이동하며 택배를 회수한다. 맨 마지막 집에서 앞 순서인 N-2번부터 0번째까지 반품할 택배를 받을 수 있을 때까지 기다리며 이동한다. 이 방식이 픽업할 수 있는 것을 먼저 픽업하는 것보다 왔다갔다 하지 않기 때문에 빠르다. 0번째 집까지 이동하며 택배를 수거했다면 위치 0까지 이동하는 시간까지 포함해주면 된다.

 

아래는 코드.

#include <iostream>
#include <utility>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;
	pair<long long, long long>* arr = new pair<long long, long long>[N];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i].first;
	}
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i].second;
	}
	long long time = max(arr[N - 1].first, arr[N - 1].second);
	for (int i = N - 2; i >= 0; i--)
	{
		long long distance = arr[i + 1].first - arr[i].first;
		if (time + distance <= arr[i].second)
		{
			time = arr[i].second;
		}
		else
		{
			time += distance;
		}
	}
	cout << time + arr[0].first << "\n";
	return 0;
}