[백준 1477번 / java] 휴게소 세우기

문제

1477번: 휴게소 세우기 (acmicpc.net)

현재 N개의 휴게소가 세워져있을 때, M개의 휴게소를 더 세워서

휴게소가 없는 구간의 최댓값이 최소가 되게 하라.

 

입력:

N(현재 휴게소 개수) M(추가할 휴게소 개수) L(고속도로 길이)

(N개의 휴게소 현재 위치)

 

출력:

M개의 휴게소를 짓고 난 후에 휴게소가 없는 구간의 최댓값의 최솟값 출력

풀이

이 문제는 매개 변수 탐색 문제이다.

그래서 접근 방법이 정해져있다.

(매개 변수 탐색 문제에 대해서는 글 하단의 유튜브 영상 참고)

 

휴게소 M개를 추가한 후에 휴게소가 없는 구간의 길이를 구해서 비교하는 방법이 아니라

휴게소가 없는 구간의 길이를 먼저 정한 다음, 해당 길이일때 휴게소가 몇 개 지어질 수 있는지 확인하는 방식으로 풀어야 한다.

 

만약 아래와 같은 값이 입력되었다면 

3 1 1000

300 701 800

 

• 처음 값, 끝 값을 붙여준다.
  •  0 300 701 800 1000
• 휴게소가 없는 구간의 길이를 모두 구한다. 
  • 300 - 0 = 300
  • 701 - 300 = 401
  • 800 - 701 = 99
  • 1000 - 800 = 200
• 모든 구간을 어떠한 길이(dist)로 나눠준다. 
  • 길이는 1~L-1 중 하나에 해당되고, 이분탐색으로 정해진다.
    • 0이 제외된 이유: 거리가 0인 것은 고려할 필요가 없음
    • L이 제외된 이유: 거리가 L인 경우는 존재하지 않음
    • 이분탐색을 시작할 때 초기값 : st = 1, en = L-1
    • 길이 : dist = (st + en) / 2
• 나눠준 값의 몫을 모두 더하여 몇 개의 휴게소가 세워질 수 있는지 구한다.
  • #1
    • st = 1, en = 999 → dist = 500
    • 300/500 + 401/500 + 99/500 + 200/500 = 0 + 0 + 0 + 0 = 0
      • 예) 구간 길이가 300인 곳의 중간에 휴게소를 세워서 길이 500을 만들 수 없다
    • dist = 500인 경우, 0개의 휴게소가 세워질 수 있다.
    • 그러나 세워져야 할 휴게소는 1개여야 하므로 (0<=1)  거리의 크기를 줄여서 더 많은 휴게소가 세워질 수 있게 만들어야 한다.
      • 따라서 이분탐색 범위를 다음과 같이 조정한다. en = dist - 1
  • #2
    • 거리의 크기가 조정되어 st = 1, en = 499 → dist = 250이 됨
    • 300/250 + 401/250 + 99/250 + 200/250 = 1 + 1 + 0 + 0 = 2
      • 예) 구간 길이가 300인 곳의 중간에 휴게소를 1개 세워서 길이를 250으로 쪼갤 수 있다
    • 2개의 휴게소가 세워질 수 있다.
    • 그러나 세워져야 할 휴게소는 1개여야 하므로 (2>1) 거리의 크기를 늘려서 더 적은 휴게소가 세워질 수 있게 만들어야 한다.
      • 따라서 이분탐색 범위를 다음과 같이 조정한다. st = dist + 1
  • #3 …
    (st ≤ en 을 만족하는 동안 반복)
  • 위 과정을 st <= en을 만족하는 동안 계속 반복하면,
    휴게소 개수가 M인 경우를 만족하는 동시에 휴게소가 없는 구간이 최소가 되는 경우가 마지막 구간으로 정의된 채 반복이 종료된다.
    • 해당 구간의 st값을 출력한다.

코드

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

public class boj_1477 {
    static int N, M, L;
    static List<Integer> location;
    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_;

        st_ = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st_.nextToken());
        M = Integer.parseInt(st_.nextToken());
        L = Integer.parseInt(st_.nextToken());

        st_ = new StringTokenizer(br.readLine());
        location = new ArrayList<>();
        for(int i=0; i<N; i++){
            location.add(Integer.parseInt(st_.nextToken()));
        }
        location.add(0);
        location.add(L);

        Collections.sort(location);

        int st = 1;
        int en = L-1;

        while(st <= en){
            int dist = (st + en) / 2; //나눌 거리의 크기
            int count = 0; //휴게소의 개수

            for(int i=0; i<location.size()-1; i++){ //현재 dist에서 몇 개의 휴게소가 세워질 수 있는지 count에 저장
                count += (location.get(i+1)-location.get(i)-1) / dist;
            }
            if(count <= M){ //세워져야 할 개수와 같거나 적게 세워졌다면
                en = dist - 1; //거리를 줄인다 //이분탐색 범위를 앞쪽으로 조정
            }else{ //많게 세워졌다면
                st = dist + 1; //거리를 늘린다 //이분탐색 범위를 뒤쪽으로 조정
            }
        }

        bw.write(st + " ");
        bw.close();

    }
}

 

Note

• 참고 강의 https://www.youtube.com/watch?v=3TkaOKHxHnI
• https://dingdingmin-back-end-developer.tistory.com/entry/%EB%B0%B1%EC%A4%80-1477-%EC%9E%90%EB%B0%94-java-%ED%9C%B4%EA%B2%8C%EC%86%8C-%EC%84%B8%EC%9A%B0%EA%B8%B0