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

문제

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

 

---

풀이

$P_A$, $P_B$에서 N개의 목적지를 전부 방문했을 때, 이동거리 총합의 최솟값과 두 지점의 이동거리 차이의 최솟값을 구하는 문제다.

우선 두 지점을 오름차순으로 교환해주고

            if (Pa > Pb) {
                int temp = Pa;
                Pa = Pb;
                Pb = temp;
            }

우선 이동거리 총합이 최소가 되야 하기 때문에 두 지점의 평균값을 기준으로 각 지점의 이동거리를 계산해준다.

            final int mid = (Pa + Pb) / 2;
            long A = 0, B = 0;
            int midCnt = 0;
            for (int x : X) {
                if (x < mid) A += (x - Pa);
                else if (x > mid) B += (Pb - x);

만약 두 지점의 이동거리가 같다면, 차이를 최소화 해야하므로 평균값과 일치하는 이동거리의 수를 세주자

                else ++midCnt;
            }

이후 평균값과 동일한 이동 거리의 수 만큼 두 이동 거리의 합에 균등하게 더해주면 된다.

            while (midCnt-- > 0) {
                if (A < B) A += (mid - Pa);
                else B += (Pb - mid);
            }

두 지점의 이동 거리는 편도를 의미하므로, 총 합과 차에 2를 곱해 출력하자.

            sb.append(2*(A + B)).append(" ").append(2*Math.abs(A - B)).append("\\n");
        }

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/27370.java