| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.5 초 | 512 MB | 221 | 113 | 85 | 50.296% |
Albert는 친구 Bob과 함께 배달 아르바이트를 해보기로 했다.
특이하게도 두 곳의 물류창고 (A 와 B) 및 배달 목적지인 $N$곳의 집들은 모두 1차원 직선상에 위치해있다. 편의상 두 물류 창고의 좌표를 $P_A$, $P_B$라 하고 $i$번째 집의 좌표를 $X_i$라 하자.
예를 들어 아래 그림은 $P_A = 0$, $P_B = 100$, $N = 4$, $X = [10, 20, 50, 60]$인 경우를 보여준다.
두 사람은 다음 규칙에 따라 배달을 해야한다:
두 사람은 배달에 관한 규칙과 지도를 확인한 후, 아래 두 조건을 만족하는 방법을 찾아보기로 했다.
위 예제에서 Albert가 1,4번 집에 배달하고 Bob이 2, 3번 집에 배달하는 경우를 살펴보자 (아래 그림 참고).
다른 방법으로 Albert가 1, 2번 집에 배달하고 Bob이 3, 4번 집에 배달하는 경우를 생각해보자. 이 경우, 아래 그림처럼 Albert는 총 60의 거리를 이동하고 Bob은 180의 거리를 이동한다. 그 합은 240이고 그 차이는 120이다.
마지막으로 Albert가 1, 2, 3번 집에 배달하고 Bob이 4번 집에 배달하는 경우를 생각해보자. 이 경우, 아래 그림처럼 Albert는 총 160의 거리를 이동하고 Bob은 80의 거리를 이동한다. 그 합은 240이고 그 차이는 80이다.
앞서 언급한 두 조건에 따르면 마지막 방법이 배달 업무를 분배하는 가장 좋은 방법이다.
입력으로 $P_A$, $P_B$, $N$, $X$가 주어졌을 때, 두 사람이 이동하는 거리의 총합이 최소가 되는 방법을 찾고, 그러한 방법이 여럿이라면 그 중 두 사람의 이동거리의 차이가 최소가 되는 방법을 찾아보자.
첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 첫 줄에는 $N$, $P_A$, $P_B$가 공백으로 구분되어 주어진다. 둘째 줄에는 목적지의 위치인 $N$개의 집 위치가 공백으로 구분되어 주어진다.
각 테스트 케이스의 결과인 두 정수를 각 줄에 출력한다. 첫 수는 두 사람의 이동거리 총합의 최솟값이고, 두 번째 수는 (두 사람의 이동거리 총합이 최솟값인 방법들 중 달성 가능한) 두 사람의 이동거리 차이의 최솟값이다.
5 4 0 100 10 20 50 60 4 0 100 40 50 60 50 9 0 100 10 20 30 20 10 20 30 20 10 5 74 1 9 2 69 5 29 3 0 100 1 2 3
240 80 360 0 340 340 92 72 12 12
예제 1: 본문에서 다루었다.
예제 2: Albert가 1, 4번 집에 배달하고 Bob이 나머지 집에 배달하면 각자의 이동거리가 180이 된다.
예제 3: 추가 설명 없음.
예제 4: $P_A > P_B$일 수 있음에 주의하자.
예제 5: 이 경우 Bob은 배달을 하지 않는다.
© 2026 주식회사 데이원컴퍼니. All Rights Reserved.