[백준] 27370번: 친구와 배달하기

문제

백준 - 27370번: 친구와 배달하기

분석

예시

Albert의 시작 위치 Pa와 Bob의 시작 위치 Pb 모두 물건이 있으므로 어느 쪽에서 배달해도 상관없고, 각 집에 한 번씩 배달된다고 할 때 두 사람이 이동하는 거리의 총합이 최소가 되는 방법을 찾는 문제이다. 그러한 방법이 여럿이라면 그 중 두 사람의 이동거리의 차이가 최소가 되는 방법을 찾는다.

문제의 조건에서 N이 최대 10^5였으므로 각각이 A와 B에 속하는 모든 경우를 따진다면 2^(10^5)가 되므로 시간초과가 날 것이라고 예측했다.

따라서 예시를 관찰해본 결과 A와 B의 중간 지점보다 출발하려는 쪽에서 가깝다면 해당 위치에서 배달하는 것이 전체 거리합을 줄이는 것에 도움이 된다는 사실을 발견했다. 한 가지 고려해야 할 것은 중간 지점에 있는 집들인데 여기서는 전체 거리합은 변하지 않기 때문에 두 사람의 이동거리의 차이를 줄이는 방안으로 생각해야 한다.

N까지 도는 for문이 가장 크기 때문에 T x O(N)이 시간 복잡도이다.

코드

해결언어 : Java

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N, pa, pb;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int T = Integer.parseInt(br.readLine());
		for (int i = 0; i < T; i++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			pa = Integer.parseInt(st.nextToken());
			pb = Integer.parseInt(st.nextToken());
			if (pa > pb) {
				int tmp = pa;
				pa = pb;
				pb = tmp;
			}
			st = new StringTokenizer(br.readLine());
			long sumA = 0, sumB = 0;
			int mid = 0;
			for (int j = 0; j < N; j++) {
				int x = Integer.parseInt(st.nextToken());
				if (x - pa < pb - x)
					sumA += (x - pa) * 2;
				else if (x - pa > pb - x)
					sumB += (pb - x) * 2;
				else
					mid += 1;
			}
			while (mid-- != 0) {
				if (sumA < sumB)
					sumA += pb - pa;
				else
					sumB += pb - pa;
			}
			sb.append(sumA + sumB).append(" ").append(Math.abs(sumA - sumB)).append("\n");
		}
		System.out.println(sb);
		br.close();
	}

}