[BOJ] 1654 랜선 자르기

문제보기

이분탐색으로 left = 0, right = 2^31 -1 로 시작해서 최적의 mid값을 구하는 문제다.

이때 mid값을 k개의 랜선길이로 나눠서 더한값(cnt)이 N 보다 클 때 

result 에  mid값을 넣어줘야하는데

cnt갯수는 같지만 최대 길이가 아닐 수 있기 때문에 max함수를 이용한다.

---

#include <vector>

#include <climits>

#include <cmath>

#include <algorithm>

using namespace std;

int main(){

int k,N;

scanf("%d%d",&k,&N);

vector<long long> a(k);

long long l = 0, r = pow(2,31)-1, m =0;

for(int i = 0;i<k;i++){

scanf("%lld",&a[i]);

}

int res = 0;

while(l <= r){

m = (l + r) / 2;

int cnt = 0;

for(int i = 0;i<k;i++){

cnt += a[i] / m;

}

if(cnt >= N){

res = max(res,(int)m);

l = m + 1;

}else{

r = m - 1;

}

}

printf("%d\n",res);

}