BOJ 3079: 입국심사

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

3079번: 입국심사

최근 실패했던 문제들을 다시금 도전해보고 있던 도중 "이 문제가 왜 실패한 문제에 있지?"싶었던 문제가 하나 있었다.

문제의 대략적인 풀이는 한번에 정답을 알아내기가 쉽지 않기 때문에 미리 정답(모든 사람이 입국심사를 받기 위해 걸리는 시간)을 결정 후 주어진 조건과 비교하여 해당 시간 안에 모든 사람이 입국심사를 받을 수 있는지 없는지에 따라 답을 이분 탐색을 통해 결정해나가는 방식을 이용한다.

처음엔 아래와 같은 코드로 AC를 받은 상태였다.

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
ll n, m;
bool chk(vector<ll> & seq, ll k) {
	ll ans = 0;
	for (int i = 0; i < seq.size(); ++i) 
		ans += k / seq[i];
	return ans >= m;
}
int main() {
	scanf("%lld %lld", &n, &m);
	vector<ll> seq(n);
	for (int i = 0; i < n; ++i)
		scanf("%lld", &seq[i]);
	ll l = 1, r = 1e18;
	ll ans = 1e18;
	while (l <= r) {
		ll mid = (l + r) / 2;
		if (chk(seq, mid)) {
				ans = min(mid, ans);
				r = mid - 1;
		}
		else l = mid + 1;
	}
	printf("%lld", ans);
}

하지만 어느날 갑자기 어떤 데이터가 추가되었는지 재채점 이후로 실패한 문제로 분류되었다.

사실 10분이 넘도록 코드를 살펴보았지만 도무지 틀린부분을 찾을 수가 없어 이분 탐색을 이용해 문제를 풀며 문제가 생길 수 있는 부분에 대해 곰곰히 생각해보았다.

 

가장 처음으로 살펴봤던 부분은 이분 탐색의 구간인 $l$과 $r$이다.

$l$의 경우 1개의 입국 심사대에 한 명의 사람이 심사를 받고자 할 때, 심사대에서 걸리는 시간이 1초인 경우가 최솟값이라고 생각하고 1로 초기화해줬다.

$r$의 경우 1개의 입국 심사대에 $10^9$명의 사람이 심사를 받고자 할 때, 심사대에서 걸리는 시간이 $10^9$초인 경우가 최댓값이라고 생각하고 $10^18$로 초기화해줬다. 정답을 저장할 변수인 $ans$ 역시 나올 수  있는 최댓값으로 초기화를 해줬다.

이곳까지 살펴봤을 때 큰 문제가 없다라는 생각을 하고 chk 함수를 살펴보기로 하였다.

 

문제가 생긴 곳이 바로 chk 함수였다. chk 함수에서 $ans$를 구하는 과정에서 어떤 문제가 생길 수 있을지에 대해 생각해보면 가장 처음 $k$에 들어오는 값이 $5\cdot 10^{17}$이라는 점이다. 만약 $10^5$개의 입국 심사대가 심사에 걸리는 시간이 모두 1초라고 가정한다면 $ans$에는 $5\cdot 10^{17} \cdot 10^5$이라는 값이 들어가야만 한다. 하지만 이는 long long 범위에서 표현할 수 없는 값이기 때문에 overflow가 발생한다. 물론 이러한 예시에 의해 틀렸을지는 조금 더 생각해봐야 할 문제겠지만, 적절한 TC를 만든다면 위와 같이 overflow가 발생하는 코드들을 WA를 받도록 만들 수 있으리라 생각하였다.

 

이에 대한 해결법으로는 chk 함수의 매 반복마다 결과값이 비교하고자 하는 값인 입국 심사를 받고자하는 사람 수와 비교하며 해당 값보다 값이 큰 경우라면 반복을 멈추고 바로 함수를 종료하는 방법을 이용하였다.

정답 코드는 아래에서 확인할 수 있다.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m;
bool chk(vector<ll> & seq, ll k) {
	ll ans = 0;
	for (int i = 0; i < seq.size(); ++i) {
		ans += k / seq[i];
    if(ans >= m) return 1;
  }
	return ans >= m;
}
int main() {
	scanf("%lld %lld", &n, &m);
	vector<ll> seq(n);
	for (int i = 0; i < n; ++i)
		scanf("%lld", &seq[i]);
	ll l = 1, r = 1e18;
	ll ans = 1e18;
	while (l <= r) {
		ll mid = (l + r) / 2;
		if (chk(seq, mid)) {
				ans = mid;
				r = mid - 1;
		}
		else l = mid + 1;
	}
	printf("%lld\n", ans);
}

바뀐 점은 위에서 설명한 chk 함수의 반복문을 중간에 빠져나갈 수 있는 조건을 붙여준 것과, 이분 탐색을 할 때 답을 갱신해주는 과정에서 굳이 $min$함수를 사용하지 않아도 되기 때문에 해당 함수 없이 코드를 작성하였다.