BOJ 20982(安全点検 (Safety Inspection)) 풀이

이미지를 누르면 문제로 이동합니다

 

문제가 일본어로 되어 있어서 난감할 수 있지만 문제를 요약해 보면,

A[i] 의 위치에 B[i] 번의 목수의 작업이 필요할 때 1의 위치에서 K명의 목수가 이동할 때 몇 번 만에 작업을 모두 끝낼 수 있는지를 출력하는 문제다. 여기서 목수는 순차대로 작업을 하는 것이 아니라 임의의 작업 지점에 갈 수 있다. 한번 이동할 때마다 1의 시간이 지나가며, 작업은 모든 목수가 동시에 진행한다.

 

이러한 문제는 전형적인 이분탐색을 이용하는 문제다.

최소 시간 이후로는 항상 조건을 성립하고, 최소 시간 이전에는 성립하지 않기 때문에 이분탐색으로 이 최소 시간을 찾아주면 된다.

그러면 이분탐색의 mid 가 주어졌을 때 mid 가 만족하는지 여부는 어떻게 찾을 수 있을까?

 

주어진 A,B 에 대해 mid 안에 해결해야 되기 때문에 A를 정렬해서 가장 먼 지점부터 목수를 보내주면 된다.

이때 보내주고, 남은 시간동안 일을 시켜 K명의 목수가 mid 만큼 움직이고 일하도록 해줬을 때,

작업이 모두 끝나 있는지를 보면 된다.

mid를 가지고 각 지점에 대한 일을 하는데 참여한 목수의 수가 K 보다 같거나 작을 경우 mid 안에 처리가 가능하다고 볼 수 있기 때문에 right을 줄여주고 그게 아니라면 left를 늘려주면서 최단 시간을 구해주면 된다.

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k;
ll inf=1e18;
ll A[1010],B[1010],C[1010];
ll func(ll md){
	ll last=n-1;
	ll cnt=0;
	if(md<=A[n-1])return 0;
	while(last>=0){
		cnt+=C[last]/(md-A[last]);
		if(C[last]%(md-A[last])!=0){
			cnt++;
			ll v=(md-A[last])-C[last]%(md-A[last]);
			while(v>0 && last>=0){
				last--;
				if(last<0)break;
				ll u=min(C[last],v);
				C[last]-=u;
				v-=u;
			}
		}else{
			last--;
		}
	}
	if(cnt<=k)return 1;
	return 0;
}
int main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k;
	ll a,b;
	for(int i=0;i<n;i++){
		cin >> A[i];
	}
	for(int i=0;i<n;i++){
		cin >> b;
		B[i]=b;
		C[i]=b;
	}

	ll le=0,ri=1e18;
	while(le<ri){
		ll mid=(le+ri)/2;
		for(int i=0;i<n;i++){
			C[i]=B[i];
		}
		if(func(mid)){
			ri=mid;
		}else{
			le=mid+1;
		}
	}
	cout << le;
}