[알고리즘] 백준 2110 공유기 설치 - 자바

공유기 설치 풀이노트 

스터디때 발표를 하기 위해 정리했던 내용을 그대로 올려본다. 발표때마다 느끼지만 왤케 더듬지..

 

문제 이해하기

가장 인접한 두 공유기 사이의 거리를 최대

→ "공유기 3개를 설치하는데 공유기 사이 거리를 크게”

 

정렬 된 집 좌표 : 1_2__4___ 8_ 9

1_ 2_______ 9 1 7 → 가장 인접한 두 공유기의 거리는 7이 아닌 1

1___ 4____ 8 3 4 → 가장 인접한 두 공유기의 거리는 4가 아닌 3

 

1. 정렬하기

house = new int[N];
        for(int i=0; i<N; i++) {
            house[i] = sc.nextInt(); 
        }
        Arrays.sort(house); // 이분 탐색하려면 무조건~

 

2. 기준점 정하기

// '거리' 가 기준!!!
        int start = 1; //최소로 이동할 수 있는 거리는 1이겠지
        int end = house[N-1] - house[0]; //최대로 이동할 수 있는 거리는 8!

 

3. 이분탐색시작

while(start <= end) { 
            int houseCnt =0;
            int mid = (start + end) /2; // 그럼 중간 값부터 탐색을 시작 
            **int installed = house[0]; // #1. 무조건 처음 집부터 해야함!**
            houseCnt++; 

            for(int i=1; i<house.length; i++) {
                **if(mid + installed <= house[i])** {//#2. 중간값 + 공유기설치한집의 좌표 보다 다음 집의 좌표가 크다면
                    installed = house[i]; 
                    houseCnt++;
                }
            }

            if(houseCnt < C) { // 공유기를 다 설치 못했다. end 갱신해서 다시
                end = mid-1; 
            }else { // 공유기 설치는 다했다. 그래도 중간값 올려서 start가 end보다 커질때까지 탐색해보기
                start = mid+1; 
                result = mid; // 일단, 답을 담아두자
            }

}

 

부분설명

int houseCnt =0;
            int mid = (start + end) /2; // 그럼 중간 값부터 탐색을 시작 
            **int installed = house[0]; // #1. 무조건 처음 집부터 해야함!**
            houseCnt++; // 공유기 한대 설치했으니까

1 2 4 → 1

1 2 8 → 1

1 2 9 → 1

1 4 8 → 3

1 4 9 → 3

1 8 9 → 1

2 4 8 → 2

2 4 9 → 2

2 8 9 → 1

4 8 9 → 1

• 모든 경우의 수를 나열해봤을 때 처음 시작은 무조건 1로 시작해야 답이 나온다. 2부터 시작하면 최댓값이 안나오는건 당연한 것 같다.
• 이렇게 나열해보니 조합으로 풀어볼 수 있지 않을까 싶어 코드를 작성해봤다.

 

조합으로도 풀 수 있을까?

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

public class BOJ_2110_공유기설치2 {
    static int N, C, result;
    static int[] array;
    static int max = Integer.MIN_VALUE;

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // 집
        C = sc.nextInt(); // 공유기 수

        array = new int[N];
        for(int i=0; i<N; i++) {
            array[i] = sc.nextInt(); 
        }
        Arrays.sort(array); // 이분 탐색하려면 무조건~

        dfs(0, 0, "");
        System.out.println(max);
    }
    static void dfs(int idx, int cnt, String str) {
        if(cnt == C) {
//            System.out.println(str);
            int arrayMin = Integer.MAX_VALUE;
            for(int i=0; i<str.length()-1; i++) {
                int a = Math.abs(str.charAt(i) - str.charAt(i+1));
                arrayMin = Math.min(arrayMin, a);
            }
            max = Math.max(max, arrayMin);

            return;
        }
        if(idx>=N)
            return;

        dfs(idx+1, cnt+1, str + array[idx]);
        dfs(idx+1, cnt, str);
    }
}

답은 메모리초과가 되었다. 만약 이 문제를 보고 누군가는 조합이라고 생각되어 문제를 풀 수도 있을 것 같다.

그런 경우는 어떻게 시간복잡도를 생각해서 문제에 접근해야할지 스터디원에게 질문을 했었는데

• 문제 조건에 입력의 개수는 적은데 주어지는 수가 많은 경우 이분탐색을 의심해보기
• 구글에 조합계산기를 검색 후 직접 검색하보면서 시간복잡도를 따져보기

아직 시간복잡도를 계산하고 그 문제를 어떻게 풀어야할지는 아직은 감이 부족한 것 같아 앞으로 만나는 문제마다 고민을 해봐야 겠다.

 

#2. 반복문 설명

for(int i=1; i<house.length; i++) {
                **if(mid + installed <= house[i])** {//#2. 중간값 + 공유기설치한집의 좌표 보다 다음 집의 좌표가 크다면
                    installed = house[i]; 
                    houseCnt++;
                }
            }

중간값 + 공유기설치한집의 좌표 보다 다음 집의 좌표가 크다면 installed값을 해당 좌표로 변경해주고 공유기를 설치했으니 hoseCnt를 올려준다.

 

#3. 마지막 조건문 설명

if(houseCnt < C) { // 공유기를 다 설치 못했다. end 갱신해서 다시
                end = mid-1; 
            }else { // 공유기 설치는 다했다. 그래도 중간값 올려서 start가 end보다 커질때까지 탐색해보기
                start = mid+1; 
                result = mid; // 일단, 답을 담아두자
            }

중간값의 변화를 출력해보면 아래와 같다.

총 반복문은 3번을 돌며 mid값은 4 -> 2 -> 3 순으로 변경되며 탐색을 한다.