[백준]#1561 놀이 공원

문제

N명의 아이들이 한 줄로 줄을 서서 놀이공원에서 1인승 놀이기구를 기다리고 있다. 이 놀이공원에는 총 M종류의 1인승 놀이기구가 있으며, 1번부터 M번까지 번호가 매겨져 있다.

모든 놀이기구는 각각 운행 시간이 정해져 있어서, 운행 시간이 지나면 탑승하고 있던 아이는 내리게 된다. 놀이 기구가 비어 있으면 현재 줄에서 가장 앞에 서 있는 아이가 빈 놀이기구에 탑승한다. 만일 여러 개의 놀이기구가 동시에 비어 있으면, 더 작은 번호가 적혀 있는 놀이기구를 먼저 탑승한다고 한다.

놀이기구가 모두 비어 있는 상태에서 첫 번째 아이가 놀이기구에 탑승한다고 할 때, 줄의 마지막 아이가 타게 되는 놀이기구의 번호를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 이하의 자연수이며, 단위는 분이다.

출력

첫째 줄에 마지막 아이가 타게 되는 놀이기구의 번호를 출력한다.

예제 입력 1

22 5
1 2 3 4 5

예제 출력 1

4

풀이

이 문제는 이분탐색 알고리즘을 이용해서 풀 수 있었다. 시간마다 놀이기구에 탑승할 수 있는 모든 사람의 수를 체크해서 이분탐색을 진행한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static int M;
    static long[] times;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);

        input = br.readLine().split(" ");
        times = new long[M];
        for(int i=0; i<M; i++) {
            times[i] = Integer.parseInt(input[i]);
        }

        if(N<=M) {      //놀이 기구에 한번에 다 탈 수 있는 경우
            System.out.println(N);
            return;
        }

        long left = 0;
        long right = (long)30*N;    //최대 시간

        while(left<=right) {
            long mid = (left+right)/2;
            long x = count(mid);
            long y = count(mid+1);

            if(x<N && y>=N) {      
                for(int i=0; i<M; i++) {
                    if((mid+1)/times[i] > mid/times[i])
                        x++;

                    if(x==N) {
                        System.out.println(i+1);
                        return;
                    }
                }
            }

            else if(x>=N)
                right = mid-1;

            else
                left = mid+1;
        }
    }

    public static long count(long time) {   //놀이기구 이용가능한 인원 수 구하는 메소드
        long cnt = 1;             //처음에는 모든 놀이기구가 비어있기 때문에 1를 더해줌

        for(int i=0; i<M; i++) {
            cnt += time/times[i];     //단위 시간 마다 탈 수 있기 때문에 나눠서 놀이기구에 승객이 탈 수 있는 횟수를 구한다.
        }

        return cnt;
    }
}