문제

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

---

입력

첫째 줄에 N과 M이 빈칸을 사이에 두고 주어진다.
둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다.

---

출력

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

---

풀이

제한조건

• (1 ≤ N ≤ 2,000,000,000)
• (1 ≤ M ≤ 10,000)
• 운행 시간은 1 이상 30 이하의 자연수이며, 단위는 분이다.

접근방법

이분탐색
N의 범위를 보면, 선형시간이 아니라 로그시간에 푸는 문제임을 알 수 있다.
즉 이분탐색을 통해 접근한다.

이분 탐색을 통해 접근해야하는 건 알았는데, 탐색하는 기준을 어떤것으로 둘 지 막막할 수 있다.
바로, 모든 사람이 놀이기구에 탑승하는 시간이다.

왜 모든 사람이 놀이기구에 탑승하는 시간을 구해야 하는가? 라고 한다면
그 시간을 알게된다면, 마지막 사람이 탑승하는 시간을 알 수 있다는 것이고,
시간을 안다는것은, 어떤 놀이기구가 해당 시간에 비어있었는지 알 수 있는것이기 때문이다.

따라서 이분탐색을 통하여 모든 사람이 놀이기구에 탑승하는 시간을 먼저 구한다.

K분에 모든 사람이 놀이기구에 탑승한다라고 가정해보자.
그럼 K-1분에 몇 사람이 놀이기구에 탑승했는지 구할 수 있다.

K : 모든 사람이 탑승한 시간.
arr : 놀이기구의 운행시간 배열
count : 누적 탑승 자 수

for(int time : arr)
	count += (k-1) / time

이제 다시 K분으로 돌아가보자.
K분에 탑승하는 사람을 찾아보자.

if(K % arr[i] == 0){
	// i+1 번째 놀이기구가 현재 탑승 가능한 상태..!
}

이제 몇 번째 놀이기구에 가장 마지막 아이가 탑승할지 찾을 수 있다.

이제 문제에서 조금 더 주의할 부분을 살펴보자.

주의1
만약 N보다 M이 큰 경우, 즉 놀이기구가 사람 수 보다 많다면, 한 번에 모두가 탈 수 있다.
해당 경우는 탐색할 필요가 없다.

주의2
N이 M보다 큰 경우, 누적 탑승자를 계산할 때, 초기에는 모든 놀이기구가 비어있기 때문에,
M명이 탑승하고 시작한다.
즉 count = M에서 시작해야한다.

주의3
C/C++, Java
N이 20억까지라고 int형으로 처리하면 안된다.
최악의 경우, N = 20억, M = 1, 운행시간 30일 경우 수의 범위가 매우 크다.
이는 이분 탐색시 right의 범위와도 연관이 있으므로 타입을 주의해서 접근해야 한다.

---

코드

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

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

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

		inputs = in.readLine().split(" ");
		arr = new int[M];
		for (int i = 0; i < M; ++i)
			arr[i] = stoi(inputs[i]);

		// 사람 수가 놀이기구의 수보다 작다면, 모두 바로 탑승 가능하다.
		if (N <= M) {
			System.out.println(N);
			return;
		}

		// 모든 사람이 탑승하게 되는 시간을 구한다.
		long left = 0;
		long right = 60000000000L;
		while (left <= right) {
			long mid = (left + right) / 2;

			long count = M;
			for (int time : arr)
				count += mid / time;

			if (count >= N)
				right = mid - 1;
			else
				left = mid + 1;
		}

		// 모든 사람이 탑승하기 바로 직전 시간에 몇 명이 탑승하였는지 확인.
		int complete = M;
		for (int time : arr)
			complete += (left - 1) / time;

		// 모든 사람이 탑승하는 시간에 빠른 번호의 놀이기구 부터 1명씩 탑승하며 확인
		int idx = -1;
		while (complete < N) {
			idx++;
			if (left % arr[idx] == 0)
				complete++;
		}
		System.out.println(idx + 1);
	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
}