BOJ 1561 놀이 공원(Java)
문제 탐색하기
N명의 아이들이 한 줄로 줄을 서서 놀이공원에서 1인승 놀이기구를 기다리고 있다. 이 놀이공원에는 총 M종류의 1인승 놀이기구가 있으며, 1번부터 M번까지 번호가 매겨져 있다.
모든 놀이기구는 각각 운행 시간이 정해져 있어서, 운행 시간이 지나면 탑승하고 있던 아이는 내리게 된다. 놀이 기구가 비어 있으면 현재 줄에서 가장 앞에 서 있는 아이가 빈 놀이기구에 탑승한다. 만일 여러 개의 놀이기구가 동시에 비어 있으면, 더 작은 번호가 적혀 있는 놀이기구를 먼저 탑승한다고 한다.
첫 번째 아이가 놀이기구에 탑승한다고 할 때, 줄의 마지막 아이가 타게 되는 놀이기구의 번호를 구하는 프로그램을 작성하시오.
- 첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다.
-
둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 이하의 자연수이며, 단위는 분이다.
- 첫째 줄에 마지막 아이가 타게 되는 놀이기구의 번호를 출력한다.
코드 설계하기
예제 입력으로 N = 22, M = 5이고 각 놀이기구의 운행시간이 1, 2, 3, 4, 5분일 때를 시뮬레이션하면 다음과 같다
| 시간\놀이기구 | 1번 | 2번 | 3번 | 4번 | 5번 |
|---|---|---|---|---|---|
| 0분 | 1 | 2 | 3 | 4 | 5 |
| 1분 | 6 | - | - | - | - |
| 2분 | 7 | 8 | - | - | - |
| 3분 | 9 | - | 10 | - | - |
| 4분 | 11 | 12 | - | 13 | - |
| 5분 | 14 | - | - | - | 15 |
| 6분 | 16 | 17 | 18 | - | - |
| 7분 | 19 | - | - | - | - |
| 8분 | 20 | 21 | - | 22 | - |
표를 분석해보면 다음과 같을 것이다:
- 0분에는 1~5번 아이들이 각각 1~5번 놀이기구에 탑승한다.
- 1분에는 1번 놀이기구가 비어 6번이 탑승한다.
- 2분에는 1번과 2번 놀이기구가 비어 7, 8번이 순서대로 탑승한다.
- 마지막 22번이 8분에 4번 놀이기구에 탑승한다
따라서 정답은 4가 된다.
구현 방법
이 문제는 이분 탐색을 활용하여 해결할 수 있다. 주요 구현 단계는 다음과 같다:
- 이분 탐색을 통한 시간 계산
left = 0,right = (N/M) * max로 초기화하여 이분 탐색을 수행한다.mid시간 동안 각 놀이기구가 태울 수 있는 아이들의 수를 계산한다.- 각 놀이기구는
mid / 운행시간만큼의 아이들을 태울 수 있다. - 초기 M명의 아이들은 0분에 바로 탑승하므로, 총 탑승 인원은
M + Σ(mid/운행시간)이다.
- 마지막 아이가 탑승하는 시점 찾기
- 이분 탐색을 통해 N명 이상을 태울 수 있는 최소 시간을 찾는다.
- 찾은 시간의 바로 이전 시간(
prevT = res - 1)까지 태운 아이들의 수를 계산한다. N - prevCnt를 통해 마지막 시간에 태워야 할 아이의 순서를 구한다.
- 마지막 아이가 탑승하는 놀이기구 찾기
- 마지막 시간에 비어있는 놀이기구를 찾는다.
- 비어있는 놀이기구는
res / 운행시간 != prevT / 운행시간인 놀이기구이다. - 비어있는 놀이기구 중에서 더 작은 번호부터 순서대로 아이들을 태운다.
시간 복잡도
- 이분 탐색: O(log((N/M) * max))
- 최대 탐색 범위는 (N/M) * max이다.
- 이분 탐색은 O(logN)의 시간 복잡도를 가진다.
- 탑승 인원 계산: O(M)
- 각 이분 탐색 단계마다 M개의 놀이기구에 대해 탑승 인원을 계산한다.
- 각 놀이기구의 탑승 인원 계산은 O(1)이다.
- 최종 놀이기구 찾기: O(M)
- 마지막 시간에 비어있는 놀이기구를 찾는 과정이다.
따라서 전체 시간 복잡도는 O(M * log((N/M) * max))이다.
- N ≤ 2,000,000,000, M ≤ 10,000이므로 시간 내에 충분히 연산이 가능하다.
정답 코드 (Java)
import java.io.*;
import java.util.*;
public class b1561 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
long N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
// 운행 시간
int[] arr = new int[M];
int max = Integer.MIN_VALUE;
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++) {
arr[i] = Integer.parseInt(st.nextToken());
max = Math.max(max, arr[i]);
}
if (N <= M) {
bw.write(N + "\n");
bw.flush();
System.exit(0);
}
long res = binarySearch(arr, N, M, max);
long prevT = res - 1;
long prevCnt = M;
long[] prevArr = new long[M];
for (int i = 0; i < M; i++) {
prevArr[i] = prevT / arr[i];
prevCnt += prevArr[i]; // 경과 시간
}
long nowNCnt = N - prevCnt;
long nowCnt = 0;
long answer = N;
for (int i = 0; i < M; i++) {
if (res / arr[i] != prevArr[i]) {
nowCnt++;
if (nowCnt == nowNCnt) {
answer = i + 1;
break;
}
}
}
bw.write(answer + "\n");
bw.flush();
br.close();
bw.close();
}
private static long binarySearch(int[] a, long N, int M, int max) {
// 마지막 사람이 타는 시간 기준으로 이분 탐색을 수행한다
long left = 0, right = (N / M) * max;
long res = 0;
// N명 이상을 태울 수 있는 최소 시간을 구한다...
while (left <= right) {
long mid = (left + right) / 2;
long cnt = M;
for (int i = 0; i < M; i++) {
cnt += mid / a[i];
}
if (N <= cnt){
res = mid;
right = mid - 1;
}else {
left = mid + 1;
}
}
return res;
}
}
Leave a comment