백준 1477번 : 휴게소 세우기 [Java]

https://www.acmicpc.net/submit/1477?solve=true

문제 탐색하기

문제는 휴게소 사이의 간격의 최대 값이 최소가 되게 하는 길이를 구해야 한다. 

 

처음에 문제가 잘 이해가 되지 않아서 풀어서 써야했다. 1번 예제를 중심으로 문제를 생각해보면

// 아래는 예제에 있는 수에 시작(0)과 끝(800)을 더해서 오름차순으로 정렬한 형태이다.

[0, 82, 201, 411, 555, 622, 755, 800]

 

먼저 두 지점 사이의 간격을 구하려면 위 배열을 i + 1번째 수에서 i번째 수를 빼서 다시 배열로 만들면 각 지점 사이의 거리가 보인다.

[82, 119, 210, 144, 67, 133, 45]

 

이렇게 바꾸니 뭔가 좀 보이는 듯 하다. 예제 1번의 답이 70인걸로 미루어보아서 이 배열을 오름차순으로 정렬하고 이후에 이분 탐색을 통해서 간격 사이의 최솟값을 추가되는 휴게소의 개수인 M과 같을 때를 계산해보면 답을 구할 수 있을 듯하다.

 

그러면 1부터 1000까지 숫자를 다 세서 추가되는 휴게소의 개수랑 비교하면 되지 않을까? 이를 이분 탐색을 통해서 구하기 위해서는

low와 high를 각각 L의 최소와 최대 값으로 잡고 시작하여 구현하면 된다. (각각 1과 L - 1이다)

 

시간복잡도

이분탐색을 사용하여 구현하는데 L의 크기 만큼 (실제로는 L - 2이지만) 이분탐색을 하고 있으니 O(log(N))이라고 볼 수 있다.

 

코드 설계하기

1. 입력을 받아서 각각의 차이 배열로 만든다. 이때의 배열을 정렬한다.

2. 이분 탐색을 구현한다 최소는 1, 최대는 L - 1로 한다. 이 때 target값과의 비교는 앞서 만든 배열을 mid 값으로 나누어 더한 값과 비교하여 처리하면 된다.

3. low가 high 보다 커지면 멈추도록 구현한다.

4. 값을 출력한다.

 

시도 회차 수정 사항

1회차

구현을 했지만 처음에 high를 L, low를 0으로 두어서 / zero 예외가 터졌다. high를 L - 1, low를 1로 수정하였다.

 

2회차

반례를 떠올려보았다. 기존의 코드에서는 N = 0일 경우에 그냥 나누도록 계산했지만 이 때문에 정해를 못구하는 듯 했다.

 

0 7 101

 

위의 반례에서 기존 코드대로 구현한다면 답은 12가 나오게 된다. 하지만 직접 생각해보면 달라진다. 101을 7로 나누면 몫은 14가 나오고 나머지가 3 남는다.

 

이 때 우리가 원하는건 최소 값이므로 7 * 14 = 98에서 7를 덜어내는 식으로 생각해보면 7 * 13 = 91 일 때 나머지는 10 이므로 가능하다. 한번 더 반복하게 되면 7  * 12 = 84이므로 나머지가 17이 되므로 몫보다 나머지가 커진다. 이 경우 휴게소가 하나 더 필요하기 때문에 불가능하다. 

 

이에 따라서 N = 0인 입력이 들어왔을때 배열을 특별히 처리하도록 로직을 수정하였다.

 

풀이

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

public class Main {
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;
        
        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        int nextInt() {
            return Integer.parseInt(next());
        }
    }
    
    static int N, M, L;
    static int[] list;
    static int[] distances;
    static int target;
    
    public static void main(String[] args) {
        FastReader fr = new FastReader();
        N = fr.nextInt();
        M = fr.nextInt();
        L = fr.nextInt();
        
        list = new int[N];
        distances = new int[N + 1];
        
        for (int i = 0; i < N; i++) {
            list[i] = fr.nextInt();
        }
        
        Arrays.sort(list);
        
        if (N != 0) {
            distances[N] = L - list[list.length - 1];
            distances[N - 1] = list[0] - 0;
        } else {
            distances[0] = L;
        }

        for (int i = 0; i < N - 1; i++) {
            distances[i] = list[i + 1] - list[i];
        }
        
        Arrays.sort(distances);
        
        int high = L - 1;
        int low = 1;
        int result = 0;
        while (low < high) {
            result = 0;
            target = (high + low) / 2;
            for (int i = 0; i < distances.length; i++) {
                result += count(distances[i]);
            }
            if (result <= M) {
                high -= 1;
            } else {
                low += 1;
            }
        }
        System.out.println(high);
    }
    
    static int count(int i) {
        if (i < target) {
            return 0;
        } else if (i % target == 0) {
            return i / target - 1;
        }
        return i / target;
    }
}