BOJ 1654 - 랜선 자르기

• 현재 선의 수 k, 목표로 하는 선의 수 n, 현재 선들의 길이가 주어질 때 선들을 일정 길이로 잘라야 하는데, n보다 크거나 같은 개수를 만들어야 하고, 일정 길이가 최대가 되도록 길이를 정해야 한다.(자르고 남는 나머지 선들은 버린다)

문제 풀이

• binary search문제인 것을 알고 접근해서 binary로 풀었다. 초기 단위 길이를 선의 길이합을 n으로 나눈 것에서 시작해 그 길이의 반을 변화량으로 두고 이분탐색했다.

• parametric search코드는 밑에서 설명하겠다.

소스코드

//binary search(?)
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef long long int lld;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	lld n, k, p=0;
	cin>>k>>n;
	vi l(k);
	for(int i=0;i<k;i++){
		cin>>l[i];
		p+=l[i];
	}
	p/=n;
	lld cnt=0, delta=p/2;
	if(p!=1 && p&1) delta++;
	while(delta>0){
		for(lld i:l) cnt+=i/p;
		if(n>cnt) p-=delta;
		else p+=delta;
		if(delta!=1 && delta&1) delta++;
		delta/=2;
		cnt=0;
	}
	for(lld i:l) cnt+=i/p;
	if(cnt<n) p--;
	cout<<p;
	return 0;
}

//parametric search
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef long long int lld;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	lld n, k, cnt=0;
	cin>>k>>n;
	vi li(k);
	for(int i=0;i<k;i++) cin>>li[i];
	lld l=1, r=1<<31-1, m;
	while(l<=r){
		m=(l+r)/2;
		for(lld i:li) cnt+=i/m;
		if(n>cnt) r=m-1;
		else l=m+1;
		cnt=0;
	}
	printf("%d", l-1);
	return 0;
}

풀고나서

• 처음 이분탐색을 할 때부터 애매한 점이 있었다. 홀수일 때 변화량의 처리와 변화량을 더할 때도 있고 뺄 때도 있어서 헷갈렸다. 풀고나서 맞은 사람들의 코드를 보면서 parametric search가 딱 들어맞는 풀이라는 것을 알게 되었다. 코드도 정말 간단해진다.

• binary search와 탐색 원리는 같은데 정확한 값을 찾는게 중요한게 아닌(존재 여부 등), 최적화시켜야하는(특정 값에 가장 가깝거나 기준 만족하는 것중 가장 큰 것 등등) 문제에 대해 parametric search를 효과적으로 사용할 수 있는 것 같다.

• bits/stdc++.h를 사용했는데 직접 헤더들을 정의하는 것에 비해 컴파일이 되게 오래걸린다.