[BOJ] 백준 1561번 놀이 공원 (Java)

#1561 놀이 공원

난이도 :  골드 2

유형 : 이분 탐색

1561번: 놀이 공원

▸ 문제

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

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

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

▸ 입력

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

▸ 출력

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

 

문제 풀이  

일단 범위가 너무 크다. 보통 10억이상이면 그냥 long으로 선언해주는 게 좋다. N명의 아이들이 놀이 기구를 차례대로 탄다. 우리는 그 마지막 싸이클을 찾아서 그 마지막 싸이클만 계산해주면 된다. 

• t라는 시간동안  N명의 이하 아이들이 놀이기구를 모두 탈 수 있는 최대의 t를 구하자.

 

먼저 t분이라는 시간동안 놀이기구를 탄 아이들의 수는 다음과 같이 구할 수 있다.

• 0분에 아이들은 차례대로 m개의 놀이기구를 탄다.
• 각 놀이기구 당 t분동안 탈 수 있는 인원의 수는 t/(놀이기구 운행시간)으로 구할 수 있다.

long childNum = m;
for(int i=0; i<m; i++) {
    childNum += t/time[i];
}

 

모든 아이들이 놀이기구를 탈 수 있는 최대 시간은 20억*30분이다.  20억명이 모두 운행 시간이 30분인 1개의 놀이기구를 이용한다면 말이다. 이것을 선형탐색으로 구한다면 시간초과가 발생하므로 이분 탐색을 통해 로그시간으로 줄여준다.

• 최소시간 0, 최대시간 n*30분
• 중간값을 구해서(mid) 그 중간값 동안 놀이기구를 탈 수 있는 아이들의 수를 구한다. (childNum)
• childNum이 n 인 구간을 출력한다.

private static long binarySearch() {
	long l = 0;
	long r = n*30;
	while(l <= r) {
		long mid = (l+r)/2;
		long childNum = getChildNumInTime(mid);
		
		if(childNum < n) {
			l = mid+1;
		}else {
			r = mid-1;
		}
	}
	return l;
}

 

 

그러면 이제 위에서 구한 시간에서 -1을 하여 마지막 전 싸이클까지 놀이기구를 탄 아이들의 수를 구해준다. 그리고 그 수를 제외하면 이젠 마지막 싸이클에 해당하는 아이들만 남게된다. 그럼 이젠 이 남은 아이들을 선형탐색으로 돌려줘서 마지막 아이가 타는 놀이기구 번호를 출력해주면 된다.

for(int i=0; i<m; i++) {
	if(result%time[i]==0) { // result에 이용가능한 놀이기구 
		child++;
	}
	if(child == n) {
		System.out.println(i+1);
		break;
	}
}

 

풀이 코드 

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

public class Main {

	static long n;
	static int m;
	static int[] time;
	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());
		
		time = new int[m];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<m; i++) {
			time[i] = Integer.parseInt(st.nextToken());
		}
		
		if(n <= m) {
			System.out.println(n);
			return;
		}
		
		long result = binarySearch();
		long child = getChildNumInTime(result-1);
		
		for(int i=0; i<m; i++) {
			if(result%time[i]==0) { // result에 이용가능한 놀이기구 
				child++;
			}
			if(child == n) {
				System.out.println(i+1);
				break;
			}
		}
	}

	private static long getChildNumInTime(long t) {
		long childNum = m;
		for(int i=0; i<m; i++) {
			childNum += t/time[i];
		}
		return childNum;
	}

	private static long binarySearch() {
		long l = 0;
		long r = n*30;
		while(l <= r) {
			long mid = (l+r)/2;
			long childNum = getChildNumInTime(mid);
			
			if(childNum < n) {
				l = mid+1;
			}else {
				r = mid-1;
			}
		}
		return l;
	}
}