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

문제 링크 - https://www.acmicpc.net/problem/1654

🌱 문제

🌱 풀이

• 이 문제를 처음 읽고 이분 탐색 문제구나! 라는 생각이 바로 들지 않았다... (힌트를 읽고 알았다.ㅠㅠ)
• 랜선의 길이가 될 수 있는것은 1부터 ~ 입력받은 랜선 길이의 최댓값이므로, 이를 각각 start, end로 지정하고 이분탐색으로 풀었다.
• 랜선의 길이는 2^31-1 보다 작거나 같은 자연수 라고 하였다.
• 2^31 = 2,147,483,648이다.
  ex) mid= (start+end)/2 인데 예를 들어 start=2, end=2,147,648 인경우 mid가 int범위를 넘어가게 되므로 long long으로 선언해 주었다.

🌱 코드

//1654번: 랜선 자르기

/*

이미 있는 랜선 K개 :
1<=k<=10,000

필요한 랜선 N개:
1 <= N <= 1,000,000

*/

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n,k;
vector<int> v;
long long answer;

void func(){
    // 랜선 길이의 최댓값은 v의 최댓값
    long long start=1;
    long long end=v[k-1];

    //여기 주의 . start==end==mid일때 mid가 최댓값으로 답일수도 있음.
    while(start<=end){
        long long mid=(start+end)/2;
        long long sum=0;
        //mid가 현재 자르려는 길이
        for(int i=0; i<k; i++){
            sum+=v[i]/mid;
        }
      
        if(sum>=n){
            if(answer<mid)
            answer=mid;

            start=mid+1;
        }else{
            end=mid-1;
        }
    }

}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>>k>>n;
    for(int i=0; i<k; i++){
        int x;
        cin>>x;
        v.push_back(x);
    }
    sort(v.begin(), v.end());

    func();
    cout<<answer<<"\n";

}