[백준 | Java] 1561 놀이공원

내 풀이

어린이의 수인 N의 범위가 (1 ≤ N ≤ 2,000,000,000)으로 최댓값이 굉장히 큰 수이다.
시간 제한은 2초이므로, 실행 시간의 효율을 위해서 모든 어린이의 놀이기구가 시작되는 시간을 기준으로 이분 탐색을 수행하여 탐색 시간을 로그 단위로 줄여나가야 한다.

풀이과정은 다음과 같다.

1. 놀이기구 운행 시간 중 가장 큰 값(maxT) 구하기
2. 운행 시간이 가장 긴 놀이기구만 모든 N이 이용한다고 가정해,
   모든 어린이의 놀이기구가 시작되는 시간을 0부터 maxT까지로 설정해 이분 탐색 수행
3. 탐색한 시간에 N개 이상의 놀이기구가 운행을 시작했을 경우,
   마지막 아이가 탑승한 놀이기구 번호 구하고 시간 줄이기
4. 탐색한 시간에 N개 이하의 놀이기구가 운행을 시작했을 경우,
   시간 늘리기

💡 해당 시간까지 운행을 시작한 놀이기구의 수 구하는 방법
1. 0분에 M개만큼 운행이 시작 (M개보다 N이 작을 때, 그대로 N이 답으로 반환)
2. (놀이기구 운행 시간 / 탐색할 시간) 연산을 해 나오는 모든 놀이기구의 값 구하기
3. 0분에 운행이 시작되는 값과 2번에서 구한 값을 모두 더하면 해당 시간까지 운행을 시작한 놀이기구의 수를 구할 수 있음

💡 마지막 아이가 탑승한 놀이기구를 구하는 방법
1. (놀이기구 운행 시간 % 탐색할 시간) 연산을 해 0이 나오는 놀이기구가 해당 시간에 시작되는 놀이기구들임
2. (모든 놀이기구가 시작되는 시간 - 1) 시간까지 운행 시작한 놀이기구의 수에서 1씩 더하며 운행 시작한 놀이기구의 수가 N과 같아질 때까지 반복문을 돌리기
3. (반복문이 끝날 때의 반복 횟수+1)이 마지막에 탑승한 놀이기구의 번호

코드

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

public class Main {
    static long N, result, mid;
    static int M, maxT;
    static int[] time;
    static List<Integer> startList;

    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());
        time = new int[M];
        maxT = 0;
        startList = new ArrayList<>();

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            time[i] = Integer.parseInt(st.nextToken());
            maxT = Math.max(time[i], maxT);
        }
        binarySearch();
        System.out.println(result);
    }

    static void binarySearch() {
        if (N <= M) {  // 사람 수가 놀이기구 수보다 적거나 같을 때 해당 번호 놀이기구 반환
            result = N;
            return;
        }
        long left = 0;
        long right = maxT * N;
        while (left <= right) {
            mid = (left + right) / 2;
            long num = countStart(mid);  // 해당 시간(mid)까지 운행 시작한 놀이기구의 수
            if (num >= N) {  // 현재 시간에 N개 이상의 놀이기구가 운행을 시작했을 경우
                getLastRide(mid);  // 마지막 아이가 탑승한 놀이기구 번호 구하기
                right = mid - 1;  // 시간 줄이기
            } else {  // 현재 시간에 N보다 적은 놀이기구가 운행을 시작했을 경우
                left = mid + 1;  // 시간 늘리기
            }
        }
    }

    static long countStart(long t) {
        long cnt = M;  // 모든 놀이기구가 한 번씩은 시작
        for (int i = 0; i < M; i++) {
            cnt += t / time[i];
        }
        return cnt;  // 해당 시간(t)까지 운행 시작한 놀이기구의 수
    }

    static void getLastRide(long t) {
        long cnt = M;  // 모든 놀이기구가 한 번씩은 시작
        for (int i = 0; i < M; i++) {
            cnt += (t - 1) / time[i];  // t-1 시간까지 운행 시작한 놀이기구의 수
        }

        for (int i = 0; i < M; i++) {
            if (t % time[i] == 0) {  // 마지막 아이가 탑승한 놀이기구의 번호를 반환
                cnt++;
                if (cnt == N) {
                    result = i + 1;
                }
            }
        }
    }
}