[백준] 1561번 놀이 공원 - Java

문제 링크

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

문제

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

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

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

입력

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

출력

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

알고리즘: 이분 탐색

풀이

이분 탐색 문제이다. 이분 탐색은 제일 먼저 최소 최대 범위와 어떤 값을 기준으로 이분 탐색을 진행할지 결정해야 한다.

이 문제는 운행 시간을 기준으로 이분 탐색을 진행하고,
최솟값은 1분 최댓값은 2000000000 * 30분이다.

먼저 N값이 M보다 작거나 같다면 처음 N명이 놀이기구에 차례대로 전부 타기 때문에 정답은 N이다.

그다음 N값이 M보다 크면 특정 시간에 총 몇 명이 놀이기구를 탔으며, 이후에 몇 번째 아이들이 몇 번 놀이기구를 탈 것인지 체크 한다.

다음 예제를 보자

N이 M보다 크다. 놀이기구를 운영한 지 8분이 지났다고 가정했을 때
8분 동안
1번 놀이기구는 총 8명 탑승 -> 1번 놀이기구는 비어있음
2번 놀이기구는 총 4명 탑승 -> 2번 놀이기구는 비어있음
3번 놀이기구는 총 3명 탑승 -> 3번 놀이기구는 탑승 중이며 2분 남음
4번 놀이기구는 총 2명 탑승 -> 4번 놀이기구는 비어있음
5번 놀이기구는 총 2명 탑승 -> 5번 놀이기구는 탑승 중이며 3분 남음

1~5번 놀이기구는 8분 동안 총 19명의 아이가 탑승했으며 비어있는 놀이기구는 1,2,4번 이다.
비어있으면 번호가 작은 놀이기구부터 탑승 해야 하기 때문에 20번 아이는 1번, 21번 아이는 2번,
22번 아이는 4번 놀이기구를 탑승하게 된다. -> 22번 아이가 마지막 아이이므로 정답은 4다.

소스 코드

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

public class Main {
    static long N;
    static int M,ans;
    static long rides[];
    public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      N = Long.parseLong(st.nextToken());
      M = Integer.parseInt(st.nextToken());
      rides = new long[M];
      StringTokenizer n_st = new StringTokenizer(br.readLine());
      for(int i=0; i<M; i++) {
          rides[i] = Long.parseLong(n_st.nextToken());
      }
      if(N<=M) ans = (int) N;
      else {
          //이분 탐색
          long min = 1;
          long max = 30 * 2000000000L;
          while(true) {
              long mid = (min + max)/2;
              long left[] = new long[M];
              long cout = 0;
              for(int i=0; i<M; i++) {
                  cout += mid/rides[i];
                  left[i] = mid%rides[i];
                  if(left[i] != 0) cout += 1;
              }
              if(cout<N) {
                  if(check(cout, left)) break;
                  else {
                      min = mid + 1;
                  }
              } else {
                  max = mid - 1;
              }
          }
      }
      System.out.println(ans);
    }
    
    static boolean check(long cout, long left[]) {
        for(int i=0; i<M; i++) {
            if(left[i] == 0) cout += 1;
            if(cout == N) {
                ans = i + 1;
                return true;
            }
        }
        return false;
    }
}