[골드 4] 공유기 설치

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

2110번: 공유기 설치

방법 1.

1 21 29 45 55 58

 

2개면 양끝이고

3개면 1 58 찍고 mid랑 제일 가까운 29고

4개면 1 58 찍고 mid에서 넓혀가면서 체크하고? -> 이게 좀 어려운데?

5개면 어떻게 하지

 

방법 2.

그냥 바보같이 완전탐색으로 일단 풀자

index 기준으로 012 013 014...처럼 모든 경우 구하기

 

N개에서 C개를 뽑는 경우의 수

근데 전체 경우의 수 만들면

2^200000 = INF 안 되겠다

 

방법 3.

2개면 양끝

3개 이상이면 긴 쪽을 골라서 가운데 추가 ( visited TFFFTFFFT 면 TT사이가 거리가 긴 곳에서)

C개까지 반복 추가

1%에서 메모리 초과

논리가 맞는지도 모르겠음

 

방법 4. 힌트 봤다

정렬하고

1 2 4 8 9

 

개수 신경 쓰지 말고 일단

(거리 = 정답)은 1부터 9-1까지 가능하다

 

1이라고 생각하면 공유기 설치를 5개 할 수 있다

8이라고 생각하면 공유기 설치를 2개 할 수 있다

 

공유기 설치가능 개수가 C개인 것을 찾아라

거리에 따라

 

ex)

거리        123456789

가능개수 544333221

C=3이라고 가정하면

 

lower_bound는 34에서 걸린다

upper_bound는 67에서 걸린다

 

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int N, C;
        int[] arr;

        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());

        /////////////////////////////////////////////////////////////////////////

        Arrays.sort(arr);

        sb.append(upper_bound(arr, C));
        System.out.println(sb);
    }

    public static int upper_bound(int[] arr, int C) {
        int low = 0;
        int high = arr[arr.length - 1] - arr[0] + 1;

        while (low + 1 < high) {
            int mid = (low + high) / 2;

            int count = 1;
            int last_router_index = 0;
            for(int i = 1; i < arr.length; i++){
                if(arr[i]- arr[last_router_index]>=mid){
                    count++;
                    last_router_index = i;
                }
            }

            if(C > count){
                high = mid;
            }
            else if(C == count){
                low = mid;
            }
            else{
                low = mid;
            }
        }

        return low;
    }
}