[BOJ] 1477. 휴게소 세우기

[작성일]

• 2022-02-17

[분류]

• 우선순위큐
• 이분탐색
  
  
  

[문제링크]

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

[요구사항]

• 휴게소와 휴게소 사이 거리 중에서 최댓값을 가장 작은 값이 되도록 휴게소를 더 세우고 답을 출력하라.
  
  
  

[풀이]

이번 문제는 신기하게도 풀이가 두 가지가 있어서 둘 다 작성해보았다.

1) 우선순위 큐를 사용하는 방법

• 길이와 나눈횟수를 저장하는 클래스로 우선순위 큐를 생성하고 입력을 모두 넣는다.
• 길이가 가장 긴 path를 꺼내서 나눈 cnt를 1추가해주고 길이도 맨 처음 길이로 되돌려서 (cnt+1)로 나눈 값으로 갱신해서 넣어준다. 이렇게 하면 그 값이 소수점이 남을 수도 있는데 이 경우에는 나중에 답을 낼 때 처리해준다.
• 최종적으로 가장 길이가 긴 값이 int 형인 경우 그대로 출력하고 소수점이 붙어있을 경우 +1 해서 출력해준다.

2) 이분탐색을 이용한 방법

• 여기서는 제일 긴 것을 계속 보면서 m번 시도하는 것이 아니라 아예 길이를 계속 구해봐서 m으로 개수가 맞을 때까지 구하는 방식이다.
• mid 값을 구하는 이분탐색을 계속 시도하면서 최적의 길이를 구한다.

[코드 - 우선순위큐]

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

public class Main {
    static int N, M, L;
    static PriorityQueue<Path> pq = new PriorityQueue<>();

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());

        if (N != 0) {
            st = new StringTokenizer(br.readLine());
            int[] rest = new int[N];
            for (int i = 0; i < N; i++) {
                rest[i] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(rest);

            // 길이와 나눈횟수(처음에는 1)를 저장
            for (int i = 0; i < N - 1; i++) {
                pq.add(new Path(rest[i + 1] - rest[i], 1));
            }
            pq.add(new Path(rest[0], 1));
            pq.add(new Path(L - rest[N - 1], 1));
        } else {
            pq.add(new Path(L, 1));
        }


        // 가장 길이가 긴 것을 꺼내서 나누는 횟수를 추가해준다
        for (int i = 0; i < M; i++) {
            Path path = pq.poll();
            double dis = path.dis;
            int cnt = path.cnt;

            pq.add(new Path((dis * cnt) / (cnt + 1), cnt + 1));
        }

        // 길이 값이 소수점이 달려있으면 a, a+1로 나뉜 것이기 때문에 int형 변환 후 +1 필요
        double dis = pq.poll().dis;
        int ans = (int) dis;
        if (ans == dis) System.out.println(ans);
        else System.out.println(ans + 1);
    }
}

class Path implements Comparable<Path> {
    double dis;
    int cnt;

    public Path(double dis, int cnt) {
        this.dis = dis;
        this.cnt = cnt;
    }

    @Override
    public int compareTo(Path p) {
        return Double.compare(p.dis, this.dis);
    }
}

[코드 - 이분탐색]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    static int N, M, L;

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());

        ArrayList<Integer> list = new ArrayList<>();
        list.add(0);
        list.add(L);
        if (N != 0) {
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                list.add(Integer.parseInt(st.nextToken()));
            }
            Collections.sort(list);
        }
        int[] rest = list.stream().mapToInt(i -> i).toArray();

        // m을 찾기위해 이분탐색
        // left가 1부터 시작인 이유는 right만 계속 줄어들어서 mid가 0이 되는 경우가 발생할 수 있기 때문이다.
        int left = 1, right = L;
        while (left <= right) {
            int mid = (left + right) / 2;

            // m보다 클경우
            if (getCnt(mid, rest) > M) {
                left = mid + 1;
            }
            // m이하일 경우
            else {
                right = mid - 1;
            }
        }
        System.out.println(left);
    }

    public static int getCnt(int mid, int[] rest) {
        int count = 0;
        for (int i = 0; i < rest.length - 1; i++) {
            count += (rest[i + 1] - rest[i] - 1) / mid;
        }
        return count;
    }
}

[느낀점]

이분 탐색의 원리는 굉장히 쉽지만 이분탐색 문제인지 판별하고 실제로 적용하는 것이 굉장히 어려운 것 같다. 특히 while문 조건과 left, right의 갱신부분은 문제마다 미세하게 달라서 신경을 잘 써야겠다.