1654 랜선자르기

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
int k, n;

unsigned int maxi = 0;


int main() {
int maxint = 2147483647;
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> k >> n;
vector <int> arr;
for (int i = 0; i < k; i++) {
int mem;
cin >> mem;
arr.push_back(mem);
}
unsigned int first = 1;
unsigned int last = maxint;

while (first <= last) {
unsigned int mid = (first + last) / 2;
int count = 0;
int mem = arr.size();

for (int i = 0; i < mem; i++) {
count = count + (arr[i] / mid);
}
int key;
if (count >= n)key = 1;
else key = 0;

if (key) {
if (maxi < mid)maxi = mid;
first = mid + 1;
}
else last = mid - 1;
}



cout << maxi;

}

 

문제 요구조건대로 구현만 하면 되는 문제이지만 

이분탐색 사용

int형 오버플로우

를 신경써주어야 한다.

이분탐색을 재귀함수로 만들고 그안에 랜선을 만들어보는 함수를 넣으니 

프로그램이 심각하게 무거워져서 2100KB 로 돌릴수있는 걸 128MB로도 못돌리는 현상이 나타남

사용자 정의 함수들을 싹다 메인함수에서 반복문으로 돌려서 해결