루미 알고리즘

#1094골드반품 회수반품 회수

KOI 2024 1차코딩초등부 3번, 고등부 1번출제 한국정보올림피아드위원회이 문제가 어렵다면 — 배우는 순서 보기

원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)

반품 회수

원제: 반품 회수

문제

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

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

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

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

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

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 1≤N≤3 0001 \le N \le 3\,000
  • 1≤X1<X2<⋯<XN≤1081 \le X_1 < X_2 < \cdots < X_N \le 10^8
  • 0≤Ti≤1080 \le T_i \le 10^8 (1≤i≤N)(1 \le i \le N)

부분문제

  1. (10점) N=2N = 2
  2. (15점) N≤9N \le 9
  3. (5점) 모든 1≤i≤N1 \le i \le N에 대해 Ti=0T_i = 0
  4. (25점) 모든 2≤i≤N2 \le i \le N에 대해 Ti−1≤TiT_{i-1} \le T_i
  5. (45점) 추가 제약 조건 없음

입력 형식

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

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

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

출력 형식

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

예제

예제 1

입력
4
2 5 7 10
20 4 16 11
출력
23

예제 2

입력
3
1 2 3
3 2 1
출력
6

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2024년 1차 대회 · 원문 페이지 · 이용 조건 CC BY-NC-SA 4.0 · 원문 그대로 실었으며 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제. 비영리 목적으로만 이용할 수 있습니다.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.