1561 놀이 공원

 

1. 풀이

 

다른 블로그를 참고했다.

 

예제 3을 가지고 설명하겠다.

 

22 5
1 2 3 4 5

 

 

1) 시간에 따른 놀이기구 이용 상황

 

아이들이 22명 있고, 놀이기구가 5개 있다.

시간에 따른 아이들의 놀이기구 이용 상황을 표로 나타내면 다음과 같다.

 

즉, 맨 처음 0분에는 5명의 아이들이 각 놀이기구에 탑승한다.

1분 뒤에는 1번 놀이기구를 이용할 수 있고,

2분 뒤에는 1번, 2번 놀이기구를 이용할 수 있다.

 

 

위에서 보면 아이들이 놀이기구를 모두 탑승했을 때의 시간이 8분이다.

이 시간을 이분탐색을 이용하여 찾아낼 것이다. 

 

8이라는 숫자로 어떻게 정답, 즉 마지막 아이가 타게 되는 놀이기구 번호를 찾는지 살펴보자

 

일단 8분보다 1분 작은 7분동안 몇 명의 아이들이 놀이기구에 탑승하는지 살펴보자.

일단 0분에는 각 놀이기구를 모두 이용할 수 있기 때문에 5명의 아이들이 탑승한다.

1분부터 7분까지 각 놀이기구에 탑승하는 아이들 수는 아래의 식으로 알 수 있다.

 

=> 7분/ 각 놀이기구의 운행시간 (결과에서 정수부분만 이용)

 

1번 놀이기구 : 7/1 = 7명

즉, 1분부터 7분까지 7명이 탈 수 있다.

 

2번 놀이기구 : 7/2 = 3.5 => 3명

즉, 1분부터 7분까지 3명이 탈 수 있다.

 

때문에 0분부터 7분까지 놀이기구에 탑승하는 아이들의 수는

총 19명이 됨을 알 수 있다.

 

이제 정답을 찾기 위해

22번째 아이가 탑승하는 놀이기구 번호를 찾아야 한다.

20, 21, 22 번째 아이가 8분이 되면 놀이기구에 탑승한다.

그런데 5개의 놀이기구 중 1번, 2번, 4번 놀이기구에 탑승하고 있다.

 

1번 놀이기구의 운행시간은 1분,

2번 놀이기구의 운행시간은 2분

이런 식인데

 

8로 1,2,3,4,5 를 나누었을 때 나머지가 0인 것은 1,2,4임을 알 수 있다.

즉, 각 시간에 탑승할 수 있는 놀이기구는 

 

분/ 운행시간 => 나머지가 0인 경우 

 

그렇다면 8로 나눠서 나머지가 0인 마지막 놀이기구 번호를 출력하면 답이된다.

 

 

2) 이분탐색

이분탐색을 통해 8분,

즉 모든 아이들이 놀이기구에 탑승했을 때의 시간을 찾아보자.

 

변수 left, right, middle 을 이용한다.

이 변수들은 놀이기구 이용시간을 의미한다.

 

처음에

left = 0,

right = (N*max) / M

middle = (left+right) / 2

 

right 는 모든 아이들이 놀이기구를 탑승했을 때 걸릴 최대 시간을 계산해본다.

max 는 놀이기구 운행시간 중 최고값, 여기서는 5가 된다.

 

즉, 22명의 아이들이 놀이기구를 이용하는데,

모든 놀이기구의 운행시간을 5분이라 하고 계산하는 것이다.

 

22명이 5분씩 걸리는 놀이기구를 타므로,

22*5 를 해야되고

이런 놀이기구가 5개 있으므로

(22*5) / 5

해준다고 생각하면 된다.

 

2-1) while 문

 

이 예제에서 

left = 0, right = 22, middle = 11 이 된다.

 

그러면 middle 이라는 시간에 놀이기구에 탑승할 수 있는 아이들의 수를 세어본다.

0분에는 M 명, 즉 5명이 타므로 일단 5를 더해준다.

 

=> 탑승한 아이들의 수 : 5

 

그 후 1분부터 middle 시간동안 각 놀이기구에 탑승할 수 있는 아이들의 수는 

middle/ 각 놀이기구 운행시간 

이라고 위에서 설명했다.

 

=> 탑승한 아이들 수 : 5 + middle / 1 + middle/2 + middle/ 3 + middle /4 + middle/5 

= 5 +11+ 5+ 3+ 2+ 2

= 28

 

그러면 우리가 찾고자 하는 값은 22인데, 이보다 크기 때문에,

즉 22명의 아이들만 탑승시키면 되는데, 28명이 탑승했기 때문에

시간을 줄이면 탑승하는 아이들의 수를 줄일 수 있다.

 

그래서 right = middle -1 로 해준 뒤 다시 이분탐색을 하면 된다.

 

이런식으로 이분탐색을 해주면서 8을 찾아내면 된다.

 

 

2. 최종 코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static long N;
	static int M;
	static int max;
	static int time[];
	static long result;
	
	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+1];
		max = -1;
		
		st = new StringTokenizer(br.readLine(), " ");
		
		for(int i=1; i<=M; i++) {
			time[i] = Integer.parseInt(st.nextToken());
			max = Math.max(max, time[i]);
		}
		
		if(N<=M) {
			System.out.println(N);
			return;
		}
		
		result = 0;
		solve();
		
		long sum = M;
		
		for(int i=1; i<=M; i++) {
			
			sum+= (result-1)/time[i];
		}
		
		for(int i=1; i<=M; i++) {
			
			if(result%time[i] ==0) {
				sum++;
				
				if(sum== N) {
					System.out.println(i);
					return;
				}
			}
		}
	}
	
	public static void solve() {
		
		long left = 0;
		long right = (N*max)/M;		
		
		
		while(left <= right) {
			
			long middle = (left + right) / 2;
			long number = M;
			
			for(int i=1; i<=M; i++) {
				number+=middle/time[i];
			}
		
			
			if(number <N)  {
			
				left = middle +1;
				
			}else {
					
				right = middle-1;
			}
		}
		
		result = left;
	}
}

 

 

참고 블로그 : 

https://lotuslee.tistory.com/91

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