[백준] 1477 휴게소 세우기 (java)

이번 문제는 정말정말정말 어려웠다.
근데 검색하니까 골드 수준이 아니라는 의견이 많아 슬펐음 진짜로 슬펐다...
개인적으로 저번에 풀었던 플레 문제보다 딱 2배 어려웠던 거 같다.

왜 어려웠을까 생각을 해보면
🚨 일단 이분탐색 떠올리기가 어렵고 휴게소가 없는 거리를 왜 같은 구간으로 나누지? 여기서 이해가 어려움 (난 처음에 이해하기를 포기함)

그래서 진지하게 문제를 좀 분석하고 이분탐색으로 접근하는 방법, 사고 등을 기록하기 위해 오랜만에 포스팅을 쓴다. (+이거 안 하고 넘어가면 코딩테스트 그냥 포기할 듯 ㅠㅠㅠ 이문제 너무너무 괴롭고 빨리 끝내고싶다!!! 🥺🥺🥺)

1477 백준

1. 처음 접근법

우선순위 큐를 사용해서 구간(시작지점, 끝나는 지점, 거리)를 클래스화 하고 이를 정렬하며 그때그때 반으로 나눠주면 되지 않을까 했음

-> 안됨. 생각해보니 구간을 반으로 나눈다는 게 문제를 이해하지 못한 것... 구간 안에 여러 휴게소를 세울 수 있는데 항상 반으로 나눈다는 게 최댓값을 계산할 수 없고 문제에 맞지 않는다.

2. 이분탐색 아이디어

1에서 하루가 지나서 검색하기로 함.

1에서 문제를 해결하지 못했던 이유가 시작지점, 끝나는 지점과 같이 길이가 아니라 구간에 대해 생각했기 때문임. 구하려는 것은 휴게소가 없는 구간의 길이의 최댓값의 최솟값 인데 나는 구간의 길이가 아니라 구간 자체만을 생각했음.

👉🏻 이분탐색을 이용하여 휴게소가 없는 구간의 길이를 늘리고 줄이면서 해당 길이의 최댓값의 최솟값을 찾을 수 있다.

3. 고려사항

이분탐색의 left, right는 현재 구간 길이의 최댓값, 최솟값으로 설정

left=구간이 0인 경우는 세우지 않는 거니까 1부터
right=l-1

조건 보면 1 ≤ 휴게소의 위치 ≤ L-1 라고 되어있음
그래서 l-1-1+1 = l-1
로 최대 구간의 길이는 1부터 L-1까지의 길이임(둘 다 포함)

현재 길이를 이 중간값으로 계산하는 반복문 작성 (이게 이분탐색 과정)
-> 여기서 cnt>m, cnt<=m 고려 필요함

cnt>m인 경우, 현재 길이로 휴게소가 없는 구간을 분할했을 때 나와야 할 m보다 많다는 건 길이가 너무 짧다는 것이고 현재 구간 길이의 최댓값이 아님. 결국, 현재 길이보다 짧은 길이는 앞으로 고려하지 않도록 left=dist+1로 설정

cnt<=m인 경우, 현재 길이로 휴게소가 없는 구간을 분할했을 때 나와야 할 m보다 적다는 건 현재 길이가 너무 길다는 것이고 현재 구간 길이의 최댓값임.
이때 현재 길이보다 짧은 길이를 고려하기 위해서(우리가 구해야 하는 건 최댓값의 최솟값임) right=dist-1로 설정
+추가적으로 현재의 길이가 최댓값의 최솟값임(매번 계산하는 게 더 줄어들테니) 그래서 ans에 해당 값을 넣어줌.

🚨 여기서 어려웠던 부분은 왜 cnt<m인 경우도 정답이 될 수 있는가? 였는데
왜 m이랑 같은 값이 나왔을 때만 최솟값이 계산되어야 하는데 적게 나온 경우에 왜 최솟값을 계산하지? 라는 생각이 들었다.

하지만 우리는 같은 값으로 휴게소가 없는 구간을 분할하는데 이게 사실 이렇게 분할 안 할 수도 있고 큰 값만 이 값으로 하고 나머지는 작은 값으로 분할해서 세울 수 있는 휴게소 개수가 더욱 많이 나올 수도 있으니 그런 것이었다.

코드에 상세설명 달아놓음!

4. 코드

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

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());

        //배열 생성(고속도로 시작, 끝 고려)
        int[] ns=new int[n+2];
        ns[0]=0; ns[n+1]=l;

        //휴게소 입력
        if(n>0){
            st = new StringTokenizer(br.readLine());
            for(int i=1;i<=n;i++){
                ns[i]=Integer.parseInt(st.nextToken());
            }
        }

        //이분탐색 이용하기 전 휴게소 정렬 필수
        Arrays.sort(ns);

        //이분탐색 이용해서 "휴게소가 없는 구간의 최댓값"의 최솟값을 계산

        int left=1; 
        int right=l-1;

        int ans=0;

        while(left<=right){ //해가 존재할 때까지 반복

            int dist=(left+right)/2; //현재 구간에서 휴게소가 없는 구간 값 계산 (시작지점, 끝지점 중간 값으로)
            int cnt=countRest(dist, ns); //휴게소가 없는 구간에서 현재 dist를 기준으로 분할한다면 몇개의 휴게소를 더 세울 수 있는지 계산

            if(cnt>m){
                //더 많이 세울 수 있는 경우 = 현재 dist값이 너무 작다 = 현재 dist값을 증가시켜야 한다 (현재 dist보다 작은 것들은 고려대상에서 미포함 되도록)
                left=dist+1;

                //더 많이 세울 수 있다는 건 휴게소가 없는 구간의 최댓값이 아니라는 소리라서 별도의 처리 x
            } else{
                //현재 세우기로 한 휴게소보다 더 적게 세울 수 밖에 없는 경우 = 현재 dist 값이 너무 크다 = 현재 dist를 감소시켜야 한다 (없는 구간의 최댓값의 최솟값을 구하기 위함)
                right=dist-1;

                //현재 m값과 동일하게 휴게소를 세우거나 휴게소가 더 적게 세워지는 건 최댓값이라는 소리라서 현재의 최댓값을 정답으로 넣어줘야 함
                //왜 cnt<m일 때도 만족하는지? -> 현재는 동일한 값으로 분할한다고 가정해서 m보다 작은 거지 해당 dist가 최댓값이고 그거보다 작은 값으로 분할한다고 하면 휴게소를 m개로 세울 수 있음
                ans=dist;
            }
        }

        System.out.print(ans);
    }

    //휴게소 갯수 카운팅하는 메소드
    private static int countRest(int dist, int[] ns){
        int cnt=0;

        for(int i=0;i<=ns.length-2;i++){
            int tempDist=ns[i+1]-ns[i]; //현재 휴게소가 없는 길이 계산

            cnt+=(tempDist)/dist; //일정한 dist로 분할

            //dist로 분할 시에 딱 맞아 떨어지면 이미 휴게소가 세워져있는 구간에 휴게소를 세운다고 카운트되어서 이를 빼줌
            if (tempDist%dist==0)
                cnt--;
        }

        return cnt;
    }
}

근데 사실 억지로 이해하긴 했는데 하나의 이분탐색에서 너무 많은 걸 하려다보니 생각이 어려운 것 같다. 같은 문제를 더 풀면서 이해도를 높일 것...