[백준/C++] 1654번 랜선자르기

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

1654번: 랜선 자르기

문제요약

K개의 랜선의 길이가 주어진다. 이를 가지고 같은크기로 잘라서 N개의 작은 랜선을 만든다. 이때 만들 수 있는 최대의 길이를 출력한다.

문제 해결

유의해야할 점

랜선의 길이가 2^32-1까지 가능하다. int는 4byte이므로 양수는 2^16-1까지 가능하므로 더 큰 자료형을 써야했다. unsigned int를 사용했다.

1~(입력받은 랜선중 최대길이) 중에 이분탐색을 통해 랜선의 길이를 고르고, 몇개의 랜선이 나오는지 count했다.
여기서 주의해야할 점은 최대길이를 찾는 것이기 때문에 count를 만족해도 계속 진행해야 했었다.

#include <iostream>
#include <vector>

using namespace std;

unsigned int N, K;

int main(){
    cin >> K >> N;
    
    vector<unsigned int> arr(K);
    unsigned int max = 0;
    for(int i=0; i<K; i++){
        cin >> arr[i];
        if(max < arr[i]) max = arr[i];
    }

    unsigned int count;
    unsigned int left = 1;
    unsigned int right = max;
    unsigned int mid = (left + right) /2;
    unsigned int ans;

    do{
        count = 0;
        for(unsigned int line : arr){
            count += line / mid;
        }

        if(count >= N){  // 더 커져야 할 때
            ans = mid; 

            left = mid+1;
            mid = (left + right) / 2;
        }
        else if (count < N){    // 더 작아저야 할 때
            right = mid-1;
            mid = (left + right) / 2;
        }

    }while(left <= right);

    cout << ans;

}