1561번: 놀이 공원
첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30
www.acmicpc.net
이 문제는 이분탐색으로 모든 아이들이 다 놀이기구를 탈 수 있는 최소 시간을 구하여 풀 수 있다.
문제의 예제를 보자.
문제의 예제에서 탑승하는 아이들의 수가 22명이고, 놀이기구가 5개이며 각각의 운행시간이 1,2,3,4,5 이다.
처음 0분에 모든 놀이기구가 비어있으므로 22명 중 5명의 아이들이 각각의 놀이기구에 탑승한다.
그 다음 1분이 지난 후, 비어있는 놀이기구는 1번 놀이기구 하나뿐이다. 따라서 6번째 아이가 1번 놀이기구에 탑승한다.
이와 같은 방법으로 1분이 지날 때마다 놀이기구에 탑승하는 아이들을 표로 나타내면 아래와 같다.
즉, 8분이 지난 후에야 22명의 모든 아이들이 한번씩 놀이기구를 타게 된다.
그리고 마지막 22번의 아이는 4번 놀이기구에 탑승한다.
그렇다면 이분탐색으로 N명의 아이들이 모두 탑승할 수 있는지 아닌지를 어떻게 확인할 수 있을까?
- 처음 0분에는 모든 놀이기구의 개수만큼의 아이들이 탑승한다. 즉, 0분에는 총 M명의 아이들이
탑승이 가능하다.
- n분이 지났을 때는 각각의 놀이기구에 총 몇명의 아이들이 탑승했는지를 n/놀이기구 운행 시간(분)으로
알 수 있다. 위의 표를 보자.
놀이기구 1번 : 1분부터 8분까지 총 8명의 아이들이 놀이기구에 탑승했다.
놀이기구 1번의 운행 시간은 1분이므로 8/1 = 8명의 아이들이 탑승한 것이다.
놀이기구 2번 : 1분부터 8분까지 총 4명의 아이들이 놀이기구에 탑승했다.
놀이기구 2번의 운행 시간은 2분이므로 8/2 = 4명의 아이들이 탑승했다고 볼 수 있다.
놀이기구 3번 : 1분부터 8분까지 총 8/3 = 2명의 아이들이 탑승했다.
놀이기구 4번 : 1분부터 8분까지 총 8/4 = 2명의 아이들이 탑승했다.
놀이기구 5번 : 1분부터 8분까지 총 8/5 = 1명의 아이들이 탑승했다.
1분부터 8분까지 5개의 놀이기구에 탑승한 아이들의 수 : 8 + 4 + 2 + 2 + 1 = 17
0분에 놀이기구에 탑승한 아이들 수 : 5
즉, 8분동안 총 17 + 5 = 22명의 아이들이 탑승이 가능하다.
이분탐색 결과 모든 아이들이 탑승가능한 최소 시간은 8분이 될 것이다.
그렇다면 마지막 아이가 탄 놀이기구가 몇 번인지는 어떻게 알 수 있을까?
위의 표에서 알 수 있는 것은, n분째에는 n%놀이기구의 운행 시간(분) = 0 인 놀이기구에 새로운 아이가 탑승한다는 사실을 알 수 있다. 예를 들어, 8분에 탑승한 놀이기구를 보면, 1번, 2번, 4번이다.
각각의 운행시간은 1분, 2분, 4분으로, 8로 나누었을 때 나머지가 0이다.
n분까지 놀이기구에 탑승한 아이들의 수를 구할 수 있다면, (n-1)분까지의 놀이기구에 탑승한 아이들의 수 역시 구할 수 있을 것이다.
n분까지 놀이기구에 탑승한 아이들 수 - (n-1)분까지 놀이기구에 탑승한 아이들 수
= n분째에 놀이기구에 탑승한 아이들 수
그리고 놀이기구 1번부터 차례대로 확인하면서 운행 시간이 n분으로 나누어떨어지면 카운트를 하여서
마지막으로 n분으로 나누어 나머지가 0이 되는 놀이기구의 번호를 확인하면 된다.
소스코드 :
'BOJ' 카테고리의 다른 글
| [백준 13458번] 시험 감독 (java) (0) | 2021.03.18 |
|---|---|
| [백준 10971번] 외판원 순회 2 (java) (0) | 2021.03.18 |
| [백준 13398번] 연속합 2 (java) (0) | 2021.03.13 |
| [백준 1912번] 연속합 (java) (0) | 2021.03.13 |
| [백준 10157번] 자리배정 (java) (0) | 2021.03.10 |