백준 3079 [C++]

www.acmicpc.net/problem/3079

3079번: 입국심사

1. 풀이방법

 

- 일단, 문제를 보시면 M (친구들의 수) 가 매우 큽니다

 

- M배열같은경우 원소 하나씩 처리 (뭐 친구를 한명씩 심사대에 넣어본다거나)

 

- 이렇게 선형탐색만 해도 시간초과가 날 것입니다.  --> 이런방식은 안됨

 

- 그럼 주어진 배열의 값들로 탐색하는 것이 아닌 최소시간과 최대시간을 가지고 시간이라는 요소를 가지고 

 

- 이분탐색을 수행합니다.

 

- 시간이 주어졌을때 (시간) / (각각의 심사대에서 걸리는 시간) 을 하면 몇명을 심사할 수 있는지가 나오고

 

- 이것들을 더했을 때 주어진 시간에서의 (총 심사가능인원수)가 나오는데 이 인원이

 

- 친구들의 수 M보다 크면 심사가 되는 것이므로 결과값과 비교를 통해 넣어주고 더 적은 시간으로 가능한지를

 

- 탐색하러 떠납니다.

 

 

 

 

2. 주의사항

 

- 이분탐색 문제가 익숙치 않아서 그런지 좀 생각하는데 시간이 걸리는 것 같습니다.

 

- 그래도 저번에 www.acmicpc.net/problem/2792 (보석상자) 문제를 풀고난 후 라 조금 수월했던 것 같습니다.

 

 

 

3. 나의코드

#include<bits/stdc++.h>
using namespace std;

long long n, m,tmp;
vector<long long> commitarr;
long long resulttime=1e18;
void inputs() {
	cin >> n >> m; //n개의 심사대 , m 명의 친구들
	for (int i = 0; i < n; i++) {
		cin >> tmp; commitarr.push_back(tmp);
	}
}

void findtime(long long l, long long h)
{
	if (l > h) return;
	long long mid = (l + h) / 2;
	long long tmpsum = 0;
	for (int i = 0; i < n; i++) {
		tmpsum += (mid / commitarr[i]); //시간동안 각각의 심사대에서 심사가능인원
	}
	if (tmpsum >= m) {
		if (resulttime > mid) { resulttime = mid; } //더 적은시간으로 가능하면 갱신
		findtime(l, mid - 1);
	}
	else findtime(mid + 1, h);

}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	sort(commitarr.begin(), commitarr.end());
	long long lowtime = 1; long long hightime = commitarr[n - 1] * m;
	//가장 오래걸리는 심사대에서 모두 받을 경우가 최대
	findtime(lowtime, hightime);
	cout << resulttime;
	return 0;
}