문제

풀이

이분 탐색 말고 다른 풀이 방법도 있을것 같은데 아 잘 모르겠다. 나는 멍청한가봐. 사실 이 풀이도 888ms로 아슬아슬하게 AC 받았다.

맨 처음에 이 문제를 접했을때는 그냥 막연하게 `해쉬테이블 같은걸 사용하면 편하겠다!`라는 생각으로 <map>을 사용했었는데 당연하게도 시간 초과가 나와서 그냥 때려치고 두달동안 묵혀두다가 지금 다시 풀어봤는데 그냥 <vector> + std::sort 이분 탐색으로 풀면 될것같아서 풀어봤는데 그대로 AC가 나왔다. STL <set>으로 풀어도 될것같은데 이건 안해봤다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int t;
	scanf("%d",&t);
	while(t--){
		vector<int> seen;
		int n,m,i,x,left,right,mid,found;
		scanf("%d",&n);
		for(i=0;i<n;i++){
			scanf("%d",&x);
			seen.push_back(x);
		}
		sort(seen.begin(),seen.end());
		
		scanf("%d",&m);
		for(i=0;i<m;i++){
			scanf("%d",&x);
			found = 0;
			left = 0;
			right = n-1;
			while(left <= right){
				mid = (left+right)/2;
				if(x==seen[mid]){
					found = 1;
					break;
				}else if(x < seen[mid]) right = mid-1;
				else left = mid + 1;
			}
			printf("%d\n",found);
		}
	}
	return 0;
}

문제

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

풀이

처음으로 푼 이분 탐색 문제다. 항상 랜선을 자를수 있는 경우의 입력만 들어온다 가정하고 left를 1로, right를 가장 큰 랜선의 길이로 정한 뒤 입력받은 모든 랜선들을 mid 값(left+right를 2로 나눈 값)으로 나눈 몫을 변수에 더하고 만약 필요한 랜선의 갯수보다 같거나 많다면 ans 변수에 값을 넣고 가장 마지막에 ans 변수에 들어가있는 값을 출력하게 했다.

#include <stdio.h>
#define max(a,b) a>b?a:b
int main(){
	long long n,m[10000]={0},k,d,i,left=1,right=-1,mid,ans;
	scanf("%lld%lld",&n,&k);
	for(i=0;i<n;i++){
		scanf("%lld",&m[i]);
		right=max(right,m[i]);
	}
	while(left<=right){
		mid=(left+right)/2;
		d=0;
		for(i=0;i<n;i++) d+=m[i]/mid;
		if(d >= k){
			ans = mid;
			left = mid+1;
		}else{
			right = mid-1;
		}
	}
	printf("%lld",ans);
}

주의할 점

1. mid값으로 모든 랜선을 나눈 몫의 합이 K(필요한 랜선의 갯수)를 넘어가는 경우에도 답이 될 수 있다. 처음 제출때 이 부분을 간과하고 있다가 틀렸다.