BOJ_2110_공유기 설치 (C++, Java)

[Gold IV] 공유기 설치 - 2110

문제 링크

성능 요약

메모리: 31000 KB, 시간: 280 ms

분류

이분 탐색, 매개 변수 탐색

제출 일자

2024년 12월 3일 02:52:41

문제 설명

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x₁, ..., x_N이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력

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

출력

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

문제 풀이

집 간격 res로 이분탐색. 두가지 언어로 푸는데 50분정도 걸린 것 같다.

코드

C++코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define MOD 1000000007
#define INF LLONG_MAX
#define ALL(v) v.begin(), v.end()

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

void solve() {
    int N, C;
    cin >> N >> C;
    vector<int> arr;

    int pos;
    for (int i = 0; i < N; i++) {
        cin >> pos;
        arr.push_back(pos);
    }
    sort(ALL(arr));
    int minlen = 1;
    int maxlen = (arr[N - 1] - arr[0]) / (C - 1);
    int res = 0;

    while (minlen <= maxlen) {
        int mid = minlen + (maxlen - minlen) / 2;

        int currPos = arr[0];
        int tmpCnt = 1;
        for (int i = 1; i < N; i++) {
            if (arr[i] - currPos >= mid) {
                tmpCnt++;
                currPos = arr[i];
            }
        }

        if (tmpCnt < C) {
            maxlen = mid - 1;
        } else {
            res = mid;
            minlen = mid + 1;
        }
    }
    cout << res << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt = 1;  // 기본적으로 1번의 테스트 케이스를 처리
    // cin >> tt;    // 테스트 케이스 수 입력 (필요 시)

    while (tt--) {
        solve();
    }
    return 0;
}

---

Java코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
	static int N, C, arr[];
	public static void main(String[] args) throws Exception {
		new Main().solution();
	}

	public void solution() throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
//		br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		arr = new int[N];
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		arr = Arrays.stream(arr)
					.sorted()
					.toArray();
		
		int minLen = 1;
		int maxLen = (arr[N-1] - arr[0]) / (C-1);
		int res = 1;
		
		while(minLen <= maxLen) {
			int mid = minLen + (maxLen-minLen)/2;
			int currPos = arr[0];
			int tmpCnt = 1;
			
			for(int i=1; i<N; i++) {
				if(arr[i] - currPos >= mid) {
					tmpCnt++;
					currPos = arr[i];
				}
			}
			
			if(tmpCnt >= C) {
				res = mid;
				minLen = mid+1;
			}
			else {
				maxLen = mid-1;
			}
		}
		bw.write(String.valueOf(res));
		bw.flush();
		bw.close();
		br.close();
	}
}