[백준]1561번 놀이기구 - C/C++

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

1561번: 놀이 공원

문제

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

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

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

입력

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

출력

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

---

- N 명의 아이가 기다리는 최대 시간은 30분이 걸리는 놀이기구 1개만 있을 경우 이므로 30 * N 이다. 최소 시간은 1이다.

 

이분 탐색을 이용하여 적절한 t 값을 구하여야 한다. 이분 탐색의 두 지점을 s= 1, e = 30*n으로 설정한다. t+1에 탄 아이가 N 이상이라면 t를 저장하고 e를 t-1로 바꾼다.  N 미만이라면 s를 t+1로 바꾼다. 이를 s <=e 인 동안 진행해 준다면 최종적으로 저장된 t + 1의 시간에서 태울 수 있는 아이의 수가 N 이상 t의 시간에서는 이하가 되므로 t의 시간에 탄 아이 중에 정답이 있게 된다. 

#include <iostream>
#include <vector>

using namespace std;

int arr[10001];
long long n,m,s, e,t,cnt,result=-1;
vector <int > v;
int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) cin >> arr[i];
	if (n <= m) {
		cout << n;
		return 0;
	}
	s = 1; e = 30 * n;
	while (s <= e) {
		t = (s + e) / 2;
		cnt = 0;
		for (int i = 0; i < m; i++) {
			cnt += t / arr[i] + 1;
		}
		if (cnt >= n) {
			result = t;
			e = t - 1;
		}
		else s = t + 1;
	}
	cnt = 0;
	for (int i = 0; i < m; i++) {
		cnt += (result - 1) / arr[i] + 1;
	}
	for (int i = 0; i < m; i++) {
		if(result % arr[i] == 0) cnt++;
		if (cnt == n) {
			cout << i + 1;
			break;
		}
	}
	return 0;
}

---

    이분탐색 문제들을 풀면서 계속 봐온 문제인데 마땅히 생각나지 않아 넘겼던 문제이다. 오늘은 풀어내기 위해 보니 매개변수를 어떠한 값으로 둘지 고민을 해보니 위 문제에서 변수는 아이의 수로 두어 시간을 구하거나 혹은 시간으로 두어 아이의 수를 찾는 것이었다. 결국 우리는 아이의 수를 찾아야 하므로 시간을 매개변수로 두기로 했다. 여기까지 생각하고 푸는데 막히고 말았다. 어느 부분에서 정확히 멈춰야 할지 몰랐다. 그래서 검색을 해보니 result 값에 저장을 하는 것으로 나왔다. 하지만 확인한 블로그들이 t 초에서 태운 아이의 수를 t/arr [i] + 1로 설명하는데 의아함을 느꼈다. 해당 식으로는 위 그림에서 3초에 모든 아이가 다 타고 아이를 세면 아이의 수가 1 + 2 + 1 = 4 가 되는데 실제로는 1+ 1 + 1 = 3명이 탔기 때문이다. 이는 다들 다른 사람의 코드를 베끼는 과정에서 다들 이해하지 않고 베낀 것이 아닌가 싶다. 

   그래도 이분탐색 문제들을 계속 풀다 보니 푸는 요령이 생기는 것 같다. 문제에서 설정할 수 있는 변수들을 생각해보고 적절한 값을 설정하는 것이 중요해 보인다.