[Java] 백준 31623 - Room Temperature

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

---

풀이

입을 수 있는 재킷에 제한이 없으니, 배열의 모든 원소를 0 <= A[i] < T 값으로 만들 수 있다. (모듈러 연산)

그 후 한 명씩 재킷 하나를 입혀가며 unpleasantness 값을 계산.

unpleasantness 값은 방의 온도가 딱 중간값일 때 최소가 된다.

즉, unpleasantness = (배열의 최댓값 - 배열의 최솟값 + 1) / 2

배열의 최댓값과 최솟값을 빠르게 구하기 위해 정렬을 한다.

 

---

코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int T = Integer.parseInt(st.nextToken());
		int[] A = new int[N];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			A[i] = Integer.parseInt(st.nextToken()) % T;
		}

		Arrays.sort(A);

		int min = A[N - 1] - A[0];

		for (int i = 0; i < N - 1; i++) {
			min = Math.min(min, A[i] + T - A[i + 1]);
		}

		System.out.println((min + 1) / 2);
		br.close();
	}
}

---

후기

알고리즘 구현 능력보다는 아이디어가 필요했던 문제.