[BaekJoon] 1561 놀이 공원 (Java)

1.  문제 링크

https://www.acmicpc.net/problem/1561

2.  문제

요약

• N명의 아이들이 한 줄로 줄을 서서 놀이공원에서 1인승 놀이기구를 기다리고 있는데, 총 M종류의 1인승 놀이기구가 있으며, 1번부터 M번까지 번호가 매개져 있습니다.
• 모든 놀이기구는 각각 운행 시간이 정해져 있어, 운행 시간이 지나면 탑승하고 있던 아이는 내리게 됩니다.
• 놀이기구가 비어 있다면 현재 줄에서 가장 앞에 서 있는 아이가 빈 놀이기구에 탑승하는데, 만일 여러 개의 놀이기구가 동시에 비어 있다면 더 작은 번호가 적혀 있는 놀이기구를 먼저 탑승합니다.
• 놀이기구가 모두 비어 있는 상태에서 첫 번째 아이가 놀이기구에 탑승한다고 할 때, 줄의 마지막 아이가 타게 되는 놀이기구의 번호를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 2,000,000,000보다 작거나 같은 N과 1보다 크거나 같고 10,000보다 작거나 같은 M이 주어지고 두 번째 줄에 1보다 크거나 같고 30보다 작거나 같은 자연수인 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 주어집니다.
• 출력: 첫 번째 줄에 마지막 아이가 타게 되는 놀이기구의 번호를 출력합니다.

3.  소스코드

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

public class Main {
    static int N, M;
    static int[] times;

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        M = scanner.nextInt();
        times = new int[M];

        for(int idx = 0; idx < M; idx++)
            times[idx] = scanner.nextInt();
    }

    static void solution() {
        if(N <= M) {
            System.out.println(N);
            return;
        }

        long maxTime = (N / M) * 30L;
        long targetTime = binarySearch(0, maxTime, N);

        System.out.println(getFinalRide(targetTime));
    }

    static int getFinalRide(long targetTime) {
        int count = getPrevPeopleNum(targetTime - 1);

        for(int idx = 0; idx < M; idx++) {
            if(targetTime % times[idx] == 0) count++;
            if(count == N) return (idx + 1);
        }

        return M;
    }

    static int getPrevPeopleNum(long time) {
        int count = M;

        for(int idx = 0; idx < M; idx++)
            count += time / times[idx];

        return count;
    }

    static long binarySearch(long left, long right, int target) {
        while(left <= right) {
            long mid = (left + right) / 2;
            long sum = M;

            for(int idx = 0; idx < M; idx++)
                sum += mid / times[idx];

            if(sum < target) left = mid + 1;
            else right = mid - 1;
        }

        return left;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}