출처 : https://www.acmicpc.net/problem/1561
놀이 공원 성공
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 2881 | 553 | 370 | 19.660% |
문제
N명의 아이들이 한 줄로 줄을 서서 놀이공원에서 1인승 놀이기구를 기다리고 있다. 이 놀이공원에는 총 M종류의 1인승 놀이기구가 있으며, 1번부터 M번까지 번호가 매겨져 있다.
모든 놀이기구는 각각 정해진 운행 시간이 정해져 있어서, 운행 시간이 지나면 탑승하고 있던 아이는 내리게 된다. 놀이 기구가 비어 있으면 현재 줄에서 가장 앞에 서 있는 아이가 빈 놀이기구에 탑승한다. 만일 여러 개의 놀이기구가 동시에 비어 있으면, 더 작은 번호가 적혀 있는 놀이기구를 먼저 탑승한다고 한다.
놀이기구가 모두 비어 있는 상태에서 첫 번째 아이가 놀이기구에 탑승한다고 할 때, 줄의 마지막 아이가 타게 되는 놀이기구의 번호를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N(1<= N<= 2,000,000,000)과 M(1<= M<= 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 이하의 자연수이며, 단위는 분이다.
출력
첫째 줄에 마지막 아이가 타게 되는 놀이기구의 번호를 출력한다.
예제 입력 1
22 5 1 2 3 4 5
예제 출력 1
4
출처
Olympiad > Croatian Highschool Competitions in Informatics > 2003 > Regional Competition - Seniors 3번
풀이
시간을 이진 탐색을 이용하여 찾아낸 후에, 놀이기구를 알아내는 프로세스로 가야한다.
최대로 들어올 수 있는 시간은 놀이기구가 전부 30분이면서 N이 가장 최대일 때이기 때문에 약 60000000000정도이다.
해당 값을 right, 0을 left로 두고 현재 시간을 찾는다.
소스코드를 보면 이해가 더 쉽다.
먼저, 현재 찾는 시간을 mid 로 놓고, 해당 시간에 탑승할 수 있는 모든 사람의 수를 구한다.
구해보고 만약 N명을 태울 수 있다 즉, 탑승할 수 있는 사람의 수가 N보다 크거나 같을 경우에는 total_time을 갱신해주고 right를 갱신한다.
만약 N명을 태우지 못할 경우에는 left를 갱신한다.
이렇게 해서 총 걸리는 시간을 찾은 뒤에는 찾은 시간 - 1 분 전의 탑승 인원을 전부 체크한다.
그 다음에 찾은 시간에 나눠 떨어지는 시간이 존재하면 탑승한 사람의 수에 ++ 를 해준다.
그리고 전체 탑승한 사람의 수와 같으면 해당 인덱스가 마지막 탑승한 놀이기구 이기 때문에 해당 놀이기구를 출력해서 보여준다.
소스코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | #include <cstdio> #include <queue> #include <iostream> #include <functional> #pragma warning(disable: 4996) #define MAX_TIME 60000000000 #define MAX_M 10000 + 1 using namespace std; // global int N, M; // 0번은 사용 X int arrM[MAX_M]; int main() { scanf("%d %d", &N, &M); for (int m_idx = 1; m_idx <= M; m_idx++) { int sub_m; scanf("%d", &sub_m); arrM[m_idx] = sub_m; } // 이진탐색 // init long long left = 0; long long right = MAX_TIME; long long total_time = 0; if (N <= M) { cout << N; return 0; } // 해당 시간에 탑승할 수 있는 사람들을 세고 // N 보다 크거나 같으면 time 을 갱신한다. while (left <= right) { long long mid = (left + right) / 2; long long ridden_person = M; for (int m_idx = 1; m_idx <= M; m_idx++) { ridden_person += mid / arrM[m_idx]; } if (ridden_person>=N) { total_time = mid; right = mid - 1; } else { left = mid + 1; } } // 찾은 시간의 이전 시간까지(total_time - 1) 탑승한 인원을 전부 더한다. long long ridden_person = M; for (int m_idx = 1; m_idx <= M; m_idx++) { ridden_person += ((total_time - 1) / arrM[m_idx]); } // 찾은 시간에 탑승한 사람을 확인한다 for (int m_idx = 1; m_idx <= M; m_idx++) { if (total_time%arrM[m_idx] == 0) ridden_person++; if (ridden_person == N) { cout << m_idx << '\n'; break; } } return 0; } | cs |