[BaekJoon] 1477번 휴게소 세우기 (Java) 문제 풀이 [Gold 4]

문제

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

1477번: 휴게소 세우기

 

어떻게 풀 것인가?

https://superohinsung.tistory.com/187

[BaekJoon] 1300번 k번째 수 (Java) 문제 풀이 [Gold 2]

위 문제와 비슷한 풀이를 가진다.

 

최대 거리차가 최소가 되도록 휴게소를 M개 설치 해야한다.

-> 이분 탐색을 휴게소의 거리차를 기준으로 두어야한다.

Left와 Right를 코드에서는 변수로 두었는데, 이는 문제에서 주어진 휴게소의 위치를 뜻한다.

 

예제를 통해서 보자.

6 7 800
622 411 201 555 755 82

위와 같이 주어졌을 때

휴게소 위치를 정렬한다면

82 201 411 555 622 755

 

이후 아래 코드를 통해서 변수를 체크해보자.

 

Base : Left = 1 , Right = 799, mid = 400, sum = 0

 

while 문에 들어간 후

 

Case1 :  mid = 400, Left = 1, Right = 799 => sum = 0

Case2 :  mid = 200, Left = 1, Right = 399 => sum = 1

Case3 :  mid = 100, Left = 1, Right = 199 => sum = 5

Case4 :  mid = 50, Left = 1, Right = 99 => sum = 12

Case5 :  mid = 75, Left = 51, Right = 99 => sum = 6

Case6 :  mid = 62, Left = 51, Right = 74 => sum = 10

Case7 :  mid = 68, Left = 63, Right = 74 => sum = 8

Case8 :  mid = 71, Left = 69, Right = 74 => sum = 7

Case9 :  mid = 69, Left = 69, Right = 70 => sum = 8

Case10 :  mid = 70, Left = 70, Right = 70 => sum = 7

Result = 70

 

풀면서 놓쳤던점

처음에 문제가 말하고자하는 바를 이해하는데에 시간이 오래걸려서 문제 유형을 파악하는데 오래걸렸다.

 

이 문제를 통해 얻어갈 것

이분탐색을 이용한 응용법

 

내 코드 

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

// 백준알고리즘 1477번 휴게소 세우기

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N + 2];

        arr[0] = 0;
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        arr[N + 1] = L;
        Arrays.sort(arr);

        int left = 1;
        int right = L - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            int sum = 0;

            for (int i = 1; i < arr.length; i++) {
                sum += (arr[i] - arr[i - 1] - 1) / mid;
            }

            if (sum > M) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        System.out.println(left);
    }
}

 

참고

X