백준 - 2110번 - 공유기 설치

2110번

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

public class Main{

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int n = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());

		int[] home = new int[n];

		for (int i = 0; i<n; i++) {
			home[i] = Integer.parseInt(bf.readLine());
		}

		Arrays.sort(home);
		int max = home[n-1]-home[0]+1;
		int min = 1;
		int mid = 0;

		while (min < max) {
			long cnt = 1;
			int check = 0;
			mid = (max + min) / 2;

			for (int i = 1; i<home.length; i++) {
				if (home[i] - home[check] >= mid) {
					cnt++;
					check = i;
				}
			}

			if (cnt < c) {
				max = mid;
			}
			else {
				min = mid+1;
			}
		}

		System.out.println(min-1);
	}
}

풀이

---

0부터 백억까지나란히 줄을 지은 집이 있다. 여기서 집을 몇개 알려주고 설치할 공유기 갯수를 알려준다. 여기서 가장 인접한 두 공유기 사이의 최대 거리는 무엇인지 구하는 문제다.

사실 이 문제는 문제이해하는것이 핵심이다. 두 공유기 사이의 최대 거리 가 뭘까? 만약 이분탐색문제들을 파고있을때가 아니였다면 쉽게 생각하지 못했을것이다.

문제에 접근은 주어진 공유기 갯수와 공유기 사이의 거리를 설정했을때 몇개의 공유기가 설치되나 비교해보면서 최댓값을 찾는 식으로 하면된다. 이 접근방식이 문제의 핵심이다.

그래서 코드를 작성해보면 먼저 배열에 집의 위치를 저장하고 오름차순 정렬을 한다.

여기서 max, min을 설정해야하는데 여기서 또 잘 생각해야한다. 먼저 min은 0이 아닌 1이다. 이게 거리를 구하는 것이라 0이되면 한집에 여러개의 공유기를 설치하는 꼴이다. 그래서 한집건너 설치하는것 최소이므로 1이다.

max는 더 잘 생각해야한다. 공유기사이의 거리이기 때문에 home[n-1] - home[0]을 해야한다고 생각할것이다. 왜냐면 이게 옳바른 수 이니까 하지만 이렇게하면 while문의 조건에 걸려 마지막 반복이 수행되지 않는경우가 생긴다. 예시 2 2 '/n' 1 '/n' 10 =>9가 나와야하지만 8이나옴

그래서 max값은 home[n-1] - home[0]에 플러스 1을 해줘야한다. 이걸 이해하기까지 수많은 디버깅을 거쳤다...

교훈 : max값이나 변수를 설정할때 유동적으로 조건식에 맞는 수를 설정해야한다.
틀에 박히지말자?