[Java] 백준 2110 공유기 설치

 

문제

집 N개에 공유기 C개를 설치한다.

공유기가 설치된 거리가 가장 가까운 두 집을 골라 두 집의 거리 차를 구한 뒤에

거리의 차이가 최대가 되는 경우의 거리차를 출력하는 문제이다.

 

1) 브루트포스 방식 (X)

문제를 곧이곧대로 생각한다면 다음과 같이 풀이할 수 있다.

- N개의 집 중 공유기를 설치할 C개를 고른다 => nCc (조합)

- 모든 경우의 수에서 가장 인접한 집 2채의 거리차를 구하여 거리차의 최댓값을 리턴한다.

하지만 N과 C 범위의 최댓값(N:20만, C:20만)으로 입력이 주어진다면 시간 제한을 통과하지 못하게 된다. (20만 팩토리얼..) 따라서 해당 방식으로 문제를 풀 수 없다.

 

2) 이진탐색 방식

문제를 살짝 다르게 생각하면 이진탐색방식으로 논리를 설계할 수 있다.

문제에서 요구하는 답은 가장 인접한 두 공유기의 거리가 최대가 될 때의 '거리'이다. (두 공유기의 좌표가 아님) 따라서 '인접한 두 공유기 사이의 거리'를 탐색 기준으로 하여 이진 탐색을 해나가고, N개의 집 중 C개의 집에 공유기를 설치할 수 있는지 확인하면 된다.

 

논리는 다음과 같다.

- 탐색의 대상을 N개의 집에서 C개를 골랏을 때, '가장 인접한 집의 최소거리;로 설정한다.

- 해당 최소거리로부터 주어진 좌표에서 설치할 수 있는 공유기의 개수를 센다.

- 만약 설치가능개수가 C개 이상이라면 해당거리를 현재까지 구해진 최소거리의 최댓값과 비교한다.

이진탐색으로 풀이하면 탐색범위가 절반씩 줄어들기 때문에 시간제한 안에 문제를 풀이할 수 있다.

 

*이진탐색문제는 탐색대상을 설정하는 것이 제일 어려운것 같다...

*탐색대상을 최소거리로 놓고 공유기 설치가능 개수를 구하는 것을 구현하는 것도 꽤 어려웠다.

 

 

 

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N, C;
    static int[] houses;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 2 이상
        C = Integer.parseInt(st.nextToken()); // 2 이상
        houses = new int[N];

        for (int i = 0; i < N; i++) {
            houses[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(houses);

        // 최소 거리, 최대 거리
        int shortest = 1, longest = houses[N - 1] - houses[0];
        int result = 0;
        while (shortest <= longest) {
            int mid = (shortest + longest) / 2;

            if (isPossible(mid)) { // 공유기 C개 이상 설치 가능
                result = Math.max(result, mid);
                shortest = mid + 1;
            } else { // 공유기 C개 설치 불가
                longest = mid - 1;
            }
        }// while

        System.out.println(result);
    }// main


    static boolean isPossible(int distance) {
        int wire_cnt = 0;
        int current = 0;

        for (int i = 0; i < N; i++) {
            if (current <= houses[i]){
                wire_cnt++;
                current = houses[i] + distance;
            }
        }

        return wire_cnt >= C;
    }
}

 

 

 

채점결과