개요

백준 2110번: 공유기 설치

• 입력
  첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

• 출력
  첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

접근 방식

1. 들어온 집 좌표를 다 정렬 후, C개 이상 설치할 수있다면 해당 거리를 low로 넣어주고
   설치할 수 없다면 해당 거리를 high값에 넣어서 범위를 조절했다.
   하지만, 공유기를 몇개 설치할 수 있는지 판단 하는 과정에서
   각 좌표를 다 순환하며 차이를 다 계산해서 구하는 과정이 있었고 시간 초과가 났다.

2. 중요한건 집좌표가 아니라 공유기를 몇개 설치하느냐 이므로, 사실 집좌표는 의미가
   없고 각 집좌표의 차이가 중요하다는 걸 깨달았다.
   따라서 각 집좌표를 정렬한 후 (정렬안하고 차이를 구하면 음수인 값이 생길 수도 있다)
   각 집 좌표의 차이를 배열로 저장해서 계산을 하였다.

코드

#include<iostream>
#include<algorithm>

using namespace std;

int N, C;
int inputArr[200'001];
int inputDiffer[200'001];

void input() {
	cin >> N >> C;

	for (int i = 0; i < N; i++) {
		cin >> inputArr[i];
	}
	sort(inputArr, inputArr + N);
	for (int i = 0; i < N-1; i++) {
		inputDiffer[i]= inputArr[i+1] - inputArr[i];

	}
}

/// <summary>
/// mid값을 최대 인접거리로 정했을 때 설치한 공유기 갯수가 C개보다 많다면 true 반환, C개보다 적다면 false반환 
/// </summary>
/// <param name="mid"></param>
/// <returns></returns>
bool possible(int mid){
	//설치한 갯수, 부분합
	int amount=1,tmpSum=0;
	for (int i = 0; i < N; i++) {
		//tmpSum에 각 좌표차이값들 하나씩 더해준 후
		tmpSum += inputDiffer[i];
		//tmpSum이 mid값보다 커지면 공유기를 하나 설치해야함.
		if (tmpSum >= mid) {
			//공유기 하나 설치
			amount++;
			//설치갯수가 원하는 갯수보다 같거나 많다면 true반환-> low값 조정해서 mid값 올림
			if (amount >= C) {
				return true;
			}
			//부분합 초기화
			tmpSum = 0;
		}


	}
	//N개에 다 설치해도 C개보다 적다면 mid값 낮춰야하므로 false 반환해 high값 조정
	return false;
}

void solution() {
	int low = 0, high = 1'000'000'001,mid=0;
	while (low + 1 < high) {
		mid = (low + high) / 2;
        
		//최대값 맞춰야하므로 low값에 최대값이 들어가고, high값에 답이 안되는 값 들어감
		((possible(mid)) ? low : high) = mid;
	}
	cout << low;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	input();
	solution();
}

문풀후생

좌표에만 집착하고 어떻게 하면 각 좌표를 다 순회하면서
그 차이를 일일히 다 효율적으로 관리할수 있을까를 오래 고민하다가
종이에 간략하게 정리해보니 문득 각 좌표값의 차이가 보여서 힌트를 얻었다.

확실히 각 좌표값의 차이를 배열로 두고 문제를 푸니 확실히 코드가 간단해지고
생각할 조건들도 적어졌다.