[c++][BOJ][1654] 랜선 자르기

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

1654번: 랜선 자르기

 

특정 랜선의 개수를 입력받고 , 원하는 만큼의 개수로 나누는데 그 나누는 최대값을 구하는 문제입니다.

 

1과 가장 긴 길이의 랜선 사이를 이분탐색해서 나누면 되는 문제였습니다.

 

다만 , 랜선의 최대 길이를 고려하지 않아서 문제가 발생하는 경우가 많았습니다.

 

랜선을 계산하는 문제를 long long int 처리를 해 주어서 문제를 해결했습니다.

 

#include <iostream>
using namespace std;

long long arr[10000];

int main(){
    int n , k;
    cin >> n >> k;
    
    long long int count = 0;
    long long int maxLen = 0;
    
    for(int i=0; i<n; i++){
        cin >> arr[i];
        maxLen = max(maxLen , arr[i]);
    }
    
    long long int start = 1, end = maxLen, mid;
    
    while(start <= end){
        mid = (start + end) / 2;
        
        long long int part = 0;
        
        for(int i=0; i<n; i++){
            part += arr[i] / mid;
        }
        
        if(part >= k){
            start = mid + 1;
            count = max(count , mid);
        }
        else {
            end = mid-1;
        }
    }
    cout << count;
}