[백준 / BOJ] 1561 놀이 공원

문제

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

1561번: 놀이 공원

놀이공원에 N명의 사람과, M개의 놀이기구가 있다.

M개의 놀이기구는 각각 운행시간이 있으며, N명의 사람은 놀이기구를 "현재 탑승가능한 놀이기구중 빠른번호 순서"로 탑승하려고한다.

이때, 마지막사람이 탑승할 놀이기구의 번호를 출력하는 문제다.

 

---

풀이

처음 문제를 봤을때는, 스킵하는 방식의 dp를 이용한 문제일거라고 생각했는데, N이 최대 2,000,000,000이므로 배열선언이 안되서 DP로는 풀기 힘들어 보였다.

 

결정문제로 푼 문제다.

 

알고리즘은 아래와 같다.

시간이 T ((left+right)/2) 일때까지 놀이기구에 탑승한사람에 마지막 사람이 포함되는가? 

포함된다 -> right = T

포함되지않는다 -> left = T

 

위와 같이 구현하려면, 우선, 시간이 T일때까지 놀이기구에 탑승한 사람의 수를 구하는법을 찾아야한다.

(이제부터, 시간이 T일때까지 놀이기구에 탑승한 사람의 수를 Rider(T) 라고 하겠다.)

 

예제가

22 5

1 2 3 4 5

와 같을때,

 

1. T = 0일때, 1 2 3 4 5번 놀이기구모두 비어있으므로 탑승가능한 인원은 5명이다.

2. T = 1일때, 1번놀이기구가 운행시간 1이므로 1번 놀이기구만 탑승가능하다.

3. T = 2일때, 1번 놀이기구와 2번놀이기구가 초기화 되므로 2명 탑승가능하다.

4. T = 3일때, 1번, 3번 놀이기구가 초기화 되므로 2명 탑승 가능하다.

...

7. T = 6일때, 1번, 2번 3번 놀이기구가 초기화 되므로 3명 탑승가능하다.

 

따라서, 시간이 6일때까지(T=6일때 탑승한사람은 제외한다.) 탑승한 사람은 5+1+2+2+2+2 = 14명이며, 각 놀이기구는 T가 자신의 배수일때, 초기화된다는 사실을 알수있다.

 

즉, 시간이 T일때까지 놀이기구에 탑승한 사람의 수식은 아래와 같이 만들수있다.

 

dp : 각 시간을 가진 놀이기구가 나온횟수 예를들어,

1 5

1 1 1 3 3

의 경우 dp[1] = 2, dp[2] = 0 dp[3] = 2 가 된다.

	private long getPeople(long time){
		long ans = 0;
		boolean[] check = new boolean[35];
		for(int i = 1; i <= M; i++){
			if(check[arr[i]]) continue;
			check[arr[i]] = true;
			if(time % arr[i] == 0) ans += dp[arr[i]] * ((time / arr[i])-1);
			else ans += dp[arr[i]] * (time / arr[i]);
		}	
		return ans + M; // Time : 0 의 M명 더해줌
	}

이제 위 함수를 이용해서 이분탐색으로 물음에 답하며 답을 찾으면된다.

시간이 T ((left+right)/2) 일때까지 놀이기구에 탑승한사람에 마지막 사람이 포함되는가? 

포함된다 -> right = T

포함되지않는다 -> left = T

 

소스코드는 아래와 같다.

	private long getRiderNum(){
		if(M >= N) return N;
		long left = 0;
		long right = (N*30L);
		for(int i = 0; i < 64; i++){
			long mid = (left + right) / 2;
			if(getPeople(mid) < N && N <= getPeople(mid+1)) return findRider(mid);
			else if(getPeople(mid) < N) left = mid;
			else if(getPeople(mid) >= N) right = mid;
		}
		return findRider((left+right)/2);
	}

 

right값은 최악의경우 20억 * 30이 될수있으므로, (아래와 같은경우) 범위 설정에 유의하자.

2000000000 1

30

 

반복문을 64번 반복해주는 이유는, 매 반복마다 탐색범위가 절반으로 줄어드니,

64번 반복하면, 오차범위를 20억*30 / 2^64 로 만들수있어서 항상 정해를 구할수있기 때문이다.

 

---

https://github.com/devxb/JJUNalgo/blob/master/1561%20%EB%86%80%EC%9D%B4%20%EA%B3%B5%EC%9B%90/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃