[백준 알고리즘] 1477번 자바(Java) 휴게소 세우기

조건

문제

다솜이는 유료 고속도로를 가지고 있다. 다솜이는 현재 고속도로에 휴게소를 N개 가지고 있는데, 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어진다. 다솜이는 지금 휴게소를 M개 더 세우려고 한다.

다솜이는 이미 휴게소가 있는 곳에 휴게소를 또 세울 수 없고, 고속도로의 끝에도 휴게소를 세울 수 없다. 휴게소는 정수 위치에만 세울 수 있다.

다솜이는 이 고속도로를 이용할 때, 모든 휴게소를 방문한다. 다솜이는 휴게소를 M개 더 지어서 휴게소가 없는 구간의 길이의 최댓값을 최소로 하려고 한다. (반드시 M개를 모두 지어야 한다.)

예를 들어, 고속도로의 길이가 1000이고, 현재 휴게소가 {200, 701, 800}에 있고, 휴게소를 1개 더 세우려고 한다고 해보자.

일단, 지금 이 고속도로를 타고 달릴 때, 휴게소가 없는 구간의 최댓값은 200~701구간인 501이다. 하지만, 새로운 휴게소를 451구간에 짓게 되면, 최대가 251이 되어서 최소가 된다.

 

입력

첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다. N = 0인 경우 둘째 줄은 빈 줄이다.

출력

첫째 줄에 M개의 휴게소를 짓고 난 후에 휴게소가 없는 구간의 최댓값의 최솟값을 출력한다.

 

제한

• 0 ≤ N ≤ 50
• 1 ≤ M ≤ 100
• 100 ≤ L ≤ 1,000
• 1 ≤ 휴게소의 위치 ≤ L-1
• N+M < L
• 모든 휴게소의 위치는 중복되지 않음
• 입력으로 주어지는 모든 수는 정수

 

풀이

이 문제는 이분탐색을 하는 문제이고 휴게소간격을 조정하며 설치할 수 있는 휴게소 개수를 파악해답을 구하는 문제이다. 처음에 휴게소 위치를 배열로 입력받은후 Arrays.sort를 통해 정렬로 해준다. 이때 도로의 처음과 끝도 필요하므로
배열의 크기를[N+2]로 하고 도로의 시작과 끝인 0과 N도 추가해준다. 이를 통해 거리를 추출하고 기준mid값을 잡아준다.기준은 (left+right)/2 인값이고 거리기준값을 통해 각 거리를 나눠줘서 세울수 있는 휴게소의 갯수를 추출한다.예를 들어 거리기준이 100이고 거리가 110, 230이 있다면 각 1, 2개만큼 휴게소를 세울수있는거다(110/2 + 230/2)이것을 통해 기준거리만큼 나눴을때 세울 수 있는 휴게소가 M보다 적다면 기준값을 줄여주면 되는거고 M보다 많다면 기준값을 늘려주면된다. 근데 이제 +1씩늘리면 시간복잡도가 커지기때문에 mid = (left+right)/2 인것을 이용해 조건에 따라 left = mid 또는 right = mid 이런식으로 값을 변경해주면된다.근데 이제 조건에 맞춰서 식을 수정하면 left = mid+1 , right = mid - 1이된다.

 

아래는 현재 mid(기준거리값)을 통해 sum(세울수있는 휴게소) 를 구해서 sum>M이면 left값을 mid+1값으로 맞춰주고sum<=M이면 right = mid - 1로 맞추는 그 고정을 자세히 표현해봤다.

처음 휴게소간 거리와 while반복문 과정

 

 

 

 

 

예제 입력 예시

6 7 800
622 411 201 555 755 82

 

예제 출력 예시

70

 

소스코드

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

//1477번 휴게소 세우기

public class Main {
    public static void main(String args[]) throws IOException {
        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());  //고속도로 길이

        int[] arr = new int[N + 2];
        st = new StringTokenizer(br.readLine());
        arr[0] = 0;
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        arr[N+1] = L;
        Arrays.sort(arr);
        int[] distance = new int[N+1];
        for (int i = 1; i < arr.length; i++) {
            distance[i-1] = arr[i] - arr[i-1]-1;
        }
        int left = 1;
        int right = L-1;
        while(right>=left){
            int mid = (left+right)/2;
            int sum = 0;
            for (int i = 0; i < distance.length; i++) {
                sum += distance[i]/mid;
            }
            if(sum>M){
                left = mid+1;
            }
            else{
                right = mid-1;
            }
        }
        System.out.println(left);
    }
}

 

 

 

 

문제 출처

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

1477번: 휴게소 세우기