lango

찍먹? 부먹?
난 부먹 개발자.

2 minute read



문제 풀이

이번 문제는 이분 탐색를 잘 응용한다면 풀 수 있는 문제이다.


아이디어 도출

이분 탐색 구현도 구현이지만, N개의 집 좌표들에서 C개의 공유기를 설치하는데 최대한 설치되는 집의 거리를 벌려야 한다.

이 때, 중요한 점은 설치된 집과 설치될 집간의 최소거리를 잘 고려해야 한다.

1

1(집) 2 3 4 5(집) 6 7 8(집) 9 10 ...

위와 같이 1, 5, 8 위치에 집이 있을 경우 공유기를 1 위치인 집에 먼저 설치했다고 가정하자.

  • 두번 째 집의 위치는 5로 첫번째 집과 4만큼 거리가 떨어져 있다.
  • 세번 째 집의 위치는 8로 두번째 집과 3만큼 거리가 떨어져 있다.

이를 보면 왜 최소거리가 이 문제에서 중요한지 알 수 있을 것이다. 바로 직전에 공유기가 설치되었던 집과의 거리를 비교하며 최소 거리보다 먼 위치에 있는 집에 공유기를 설치해야 문제에서 요구하는 집 간의 거리를 벌릴 수 있게 되는 것이다.

직전에 공유기를 설치한(가장 최근에 설치한) 집과 현재 집과의 거리를 기준으로 판단해야 한다.

결국, 첫번째 집부터 공유기를 설치한 후, 첫번째 집부터 두번째 집에서 구해진 최초의 최소 거리를 기준으로 나머지 집들을 비교해가며 설치 해야할 공유기 대수(C)만큼 설치해나가면 되는 것이다.


문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

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

class Main {    

    static int[] arr;

    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int 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);

        // 최소거리가 가지는 최소값
        int min = 1;
        // 최소거리가 가지는 최대값
        int max = arr[N - 1] - arr[0] + 1;

        // Upper Bound 형식으로 이분탐색 진행
        while(min < max) {

            int mid = (min + max) / 2;

            /**
             * mid 거리에 대해서 설치 가능한 공유기 대수가 C개 미만일 경우
             * 거리를 좁혀야 하기 때문에 max를 mid로 갱신하여 줄인다.
             * 
             * 반대로, 설치 가능한 공유기 대수가 C개 초과일 경우
             * 거리를 벌리면서 최소거리가 가질 수 있는 최대거리를 찾아야 하기 때문에 min을 mid+1 값으로 늘린다.
             */
            if(ableInstall(mid) < C) {
                max = mid;
            } 
            else {
                min = mid + 1;
            }

        }
        
        // Upper Bound를 통해 탐색 값을 초과하기에 1을 뺀다.
        bw.write((min-1)+"\n");
        
        bw.close();
        br.close();
    }

    static int ableInstall(int distance) {

        // 첫번째 집은 무조건 설치하는 것을 가정한다.
        int installCnt = 1;

        // 직전에 설치한 집의 위치(최초는 첫번째 집)
        int lastPos = arr[0];

        for(int i=1; i<arr.length; i++) {

            // 현재 탐색하는 집의 위치
            int pos = arr[i];

            /**
             * 현재 탐색하는 집의 위치가 직전에 설치한 집의 위치와의 거리가 최소거리(distance)보다 크거나 같을 경우
             * 1. 현재 집에 공유기를 설치할 수 있으므로 installCnt를 1 늘려준다.
             * 2. 직전에 설치한 집의 위치인 lastPos를 갱신한다.
             */
            if(pos - lastPos >= distance) {
                installCnt++;
                lastPos = pos;
            }
            
        }

        return installCnt;

    }

}

출처

  • 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.

You may also enjoy