이분 탐색으로 최소, 최대 적절한 답 찾아내기

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int main() {
	//freopen("input.txt.txt","rt",stdin);
	
	int n, i, m, lt=1, rt, mid,sum=0 , min=100000;
	scanf("%d %d", &n, &m);
	
	vector<int> a(n+1);
	
	for(i=0; i<n; i++){
		scanf("%d", &a[i]);
		sum+=a[i];
	}
	//printf("%d\n",sum);
	rt=sum;
	while(lt<=rt){
		mid=(lt+rt)/2;
		int cnt = 1;
		int vsum = 0;
		for(i=0;i<=n;i++){
			vsum += a[i];
			if(vsum > mid){
				cnt++;
				vsum = 0;
				i--;
			}
		}
		if(m >= cnt){
			//printf("%d %d %d\n",lt,rt, mid);
			rt = mid-1;
			if(mid < min) min = mid;
			
		}
		else lt = mid+1;
	}
	printf("%d", min);
	
	// 1 2 3 4 5 6 7 8 9
	
}

 

----

함수로 깔끔하게

 

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;


//mid 숫자에서 몇개의 바구니에 들어갈 수 있는지 알아내는 함수 
int func(vector<int> &a, int mid){
	int cnt = 1;
	int vsum = 0;
	for(int i=0;i<=a.size();i++){
		vsum += a[i];
		if(vsum > mid){
			cnt++;	
			vsum = 0;
			i--;
		}
	}
	return cnt;
}


int main() {
	//freopen("input.txt.txt","rt",stdin);
	
	int n, i, m, lt=1, rt, mid,sum=0 , min=100000;
	scanf("%d %d", &n, &m);
	
	vector<int> a(n+1);
	
	for(i=0; i<n; i++){
		scanf("%d", &a[i]);
		sum+=a[i];
	}
	//printf("%d\n",sum);
	rt=sum;
	while(lt<=rt){
		mid=(lt+rt)/2;
		int cnt = func(a, mid);
		if(m >= cnt){
			//printf("%d %d %d\n",lt,rt, mid);
			rt = mid-1;
			if(mid < min) min = mid;
		}
		else lt = mid+1;
	}
	printf("%d", min);
	
	// 1 2 3 4 5 6 7 8 9
	
}

오류 있음

----------------------------------

수정

 

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int a[1001], n; 
int Count(int s){
	int i, cnt=1, sum=0;
	for(i=1; i<=n; i++){
		if(sum+a[i]>s){
			cnt++;
			sum=a[i];
		}
		else sum=sum+a[i];
	}
	return cnt;
}

int main() {
	freopen("input.txt.txt","rt",stdin);
	int m, i, lt=1, rt=0, mid, res, maxx=-1;
	scanf("%d %d", &n, &m);
	for(i=1; i<=n;i++){
		scanf("%d",&a[i]);
		rt=rt+a[i];
		if(a[i]>maxx) maxx=a[i];
	}
	while(lt<=rt){
		mid=(lt+rt)/2;
		if(mid>=maxx && Count(mid)<=m){
			rt = mid-1;
			res=mid;
		}
		else lt=mid+1;
	}
	printf("%d",res);
	
}

 

 

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

//조건에 부합하는지 check하는 함 수  
bool check(int mid, int c, vector<int> &v){
	int cur =v[0];
	int cnt = 1;
	for(int i=1; i<v.size(); i++){
		if(v[i] -cur >=mid){
			cur = v[i];
			cnt++;
		}
	}
	return cnt>=c;
}

int main() {
	freopen("input.txt.txt","rt",stdin);
	int n,c,i,res;
	scanf("%d",&n);
	scanf("%d",&c);
	
	vector<int> v(n);
	for(i=0;i<n;i++){
		scanf("%d",&v[i]);
	}
	sort(v.begin(),v.end());
	
	int mid, lt=v[0],rt=v[n-1];
	
	while(lt<=rt){
		mid=(lt+rt)/2; 
		bool how = check(mid,c,v);
		if(how){
			res = mid;
			lt = mid+1;
		}
		else{
			rt = mid-1;
		}
	}
	printf("%d\n", res);
	
}