백준 2110 - 공유기 설치

문제

 

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

2110번: 공유기 설치

 

 

풀이

결정 문제로  바꾸어 문제를 해결한다. 

이분 탐색으로 길이를 찾아가면서, 찾은 길이를 간격으로 C 개의 공유기를 설치할 수 있는지 확인한다.

 

 

코드

c++

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int N, C;
int a[200000];
int result;
 
bool check(int x)
{
    int n = 1;
    int s = 0;
    for (int i=1; i<N; i++)
    {
        if (a[i]-a[s] >= x)
        { 
            n++;
            s = i;
        }
    }
    return n >= C;
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
 
    cin >> N >> C;
 
    for (int i=0; i<N; i++) 
        cin >> a[i];
 
    sort(a, a+N);
 
    int l = 1;
    int r = a[N-1]-a[0];
 
    while (l <= r)
    {
        int m = (l+r)/2;
        if (check(m))
        {
            result = max(result, m);
            l = m+1;
        }   
        else 
            r = m-1;
    }
 
    cout << result;
 
    return 0;
}

 

java

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    static int N, C;
    static int[] a;

    public static void main(String[] args) {
        input();
        solve();
    }

    private static void solve() {
        Arrays.sort(a);
        int l = 0;
        int r = 1000000000;
        int result = 0;

        while (l <= r) {
            int mid = (l + r) / 2;
            if (determine(mid)) {
                l = mid + 1;
                result = mid;
            } else {
                r = mid - 1;
            }
        }

        System.out.println(result);
    }

    private static boolean determine(int step) {
        int cnt = 1;
        int last = 0;
        for (int i = 1; i < N; i++) {
            if (a[i] - a[last] >= step) {
                cnt++;
                last = i;
            }
        }

        return cnt >= C;
    }

    private static void input() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        C = sc.nextInt();
        a = new int[N];
        for (int i = 0; i < N; i++)
            a[i] = sc.nextInt();
        sc.close();
    }
}