[BOJ] 1183 약속 - JAVA

1. 문제

1183번: 약속

마법사 N명이 머글 문화를 이해하기 위해 머글과 약속을 잡았다. 각 마법사는 한 명의 머글을 만날 예정이다. 하지만, 마법사는 약속 시간보다 빨리 또는 늦게 도착할 수 있기 때문에 고민에 빠졌다. 결국 기다리는 시간을 최소화 하기 위해 모든 약속 시간을 T씩 미루려고 한다. 기다리는 시간은 먼저 도착한 사람이 늦게 도착한 사람이 도착할 때까지 기다리는 시간을 의미한다.
마법사의 약속 시간은 A1, A2, ..., AN이고, 도착 시간은 B1, B2, ..., BN이다. 약속 시간을 T만큼 미루면, 기다리는 시간의 합은 |Ai + T - Bi|의 합과 같다. 기다리는 시간의 합이 최소가 되는 서로 다른 정수 T의 개수를 구해보자.

---

2. 풀이

1.  A-B시간을 input배열에 저장한 뒤 정렬한다. 중간값만큼 약속시간을 이동해야 기다리는 시간의 합이 최소가 되는데, 정렬을 해야 가운데 값을 쉽게 알 수 있기 때문이다.

2.  만약 N이 홀수라면 중간 값은 하나이므로 1을 출력한다.

3.  만약 N이 짝수라면 중간 값은 input[N/2]부터 input[N/2-1]까지이므로 둘을 뺀 절대값+1이 답이다.

import java.io.*;
import java.util.*;

public class BOJ_1183_약속 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(in.readLine());
      int[] input = new int[N];
      StringTokenizer st;
      for (int i = 0; i < N; i++) {
         st = new StringTokenizer(in.readLine());
         input[i] = Integer.parseInt(st.nextToken()) - Integer.parseInt(st.nextToken());
      }
      Arrays.sort(input);

      if(N%2==1) System.out.println(1);
      else System.out.println(Math.abs(input[N/2]-input[N/2-1])+1);
   }
}

---

3. 결과

하나하나 해보다가 시간초과도 나고 메모리초과도 나봤다. 답은 내 생각보다 항상 더 간단한 것 같다.