백준 1561번 (java) 파라메트릭 서치 (이분탐색)

백준 1561번 놀이 공원 (java)

---

관찰

1. 이 문제를 처음 보면 시간이 지나가면서 선형적으로 몇 명이 탈 수 있는지 세어주는 방법을 떠올릴 수 있지만 N의 최대값이 20억이기 때문에 최대 600억번을 세어줘야 한다..

2. 이런 큰 숫자를 보게 된다면 log(n) 으로 무조건 줄여야 한다. 그런 방법 중에 하나가 바로 이분탐색이다. 이 문제에서 이분탐색을 쓰려고 한다면 파라메트릭 서치 (파라메트릭 관련 벨로그) 를 사용해서 해결할 수 있다.

3. N명의 아이까지 모두 탔을 때 T초를 구하자 가 아니라
   T초일때 N명의 아이까지 다 탈 수 있는가?
   이렇게 반전된 생각으로 이분 탐색을 적용시켜 빠르게 구해낼 수 있다.

4. 이 T초의 최대값은 600억 0부터 600억 사이를 이분탐색 해보자!

---

정답코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n,m; // 20억, 10000
    static int[] play; // 1~30
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        play = new int[m+1];
        st = new StringTokenizer(br.readLine());

        for (int i = 1; i <= m; i++) {
            play[i] = Integer.parseInt(st.nextToken());
        }

        if(n<=m){
            System.out.println(n);
        }
        else {
            long l = 0;
            long r = 60000000000L;
            long answer = 0;
            while (l <= r) {
                long mid = (l + r) / 2;
                long sum = 0;
                for(int i=1;i<=m;i++){
                    sum += (mid / play[i]) + 1;
                }
                if(n <= sum) {
                    r = mid - 1;
                    answer = mid;
                }
                else{
                    l = mid + 1;
                }
            }

            long prevSum = 0;
            for(int i=1;i<=m;i++){
                if(answer == 0){
                    prevSum += 1;
                }
                else{
                    prevSum += (answer - 1)/ play[i] + 1;
                }
            }

            long tmp = n -prevSum;

            int count = 0;
            for(int i=1;i<=m;i++){
                if(answer %play[i] == 0){
                    count++;
                    if(count == tmp){
                        System.out.println(i);
                        break;
                    }
                }
            }
        }
    }
}

---

풀이

1. 0초부터 600억초 사이에서 몇초일때 몇명이 들어갈 수 있는지를 파악하면서 N명 이상을 태울 수 있는 시간 중 최소값을 찾아준다! (answer)

2. answer-1 일때 몇 명이 들어갔는지 찾아준다. (tmp)

3. tmp를 왜 찾아줬냐면 동시에 들어갈 때 앞에서부터 빼줘야 하기 때문에 그래서 count를 세어서 몇번째 칸에서 N번째 사람이 타는지 찾아주면서 마무리

---

마무리

파라메트릭 서치는 한번 떠올리는게 항상 어려운 것 같다.
몇 초를 선형적으로 찾는 것이 아닌 전체 범위에서 이분 탐색으로 찾아주는 발상의 전환만 하면 풀 수 있는 문제였던 것 같다.