백준_1654 : 랜선 자르기 - C++

문제

 

---

문제 해석

- 입력에서 주어진 K개의 랜선을 일정한 길이로 잘라 N 개 이상의 랜선을 만드는 것이 목적이다.

---

알고리즘

- 이진 탐색으로 쉽게 해결 할 수 있다.

- 길이가 존재 해야 하므로 low 는 1, high 는 이미 가지고 있는 K 개의 랜선중 가장 길이가 긴 것으로 지정 하면 된다.

- 이 후 mid 길이만큼 실제로 랜선을 잘라 보면서 N 과 비교 해  low 나 high 를 조절 하면 된다.

---

코드

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

int K, N, ans;
long long low, high, mid;
vector<int> input;

int main(){
    cin >> K >> N;

    for(int i = 0; i < K; i++){
        int tmp;
        cin >> tmp;
        if(high < tmp){
            high = tmp;
        }
        input.push_back(tmp);
    }
    low = 1;
    ans = 0;

    while(low <= high){
        mid = (low + high) / 2;
        int cnt = 0;
        for(int i = 0; i < K; i++){
            cnt += input[i]/mid;
        }
        if(cnt >= N){
            low = mid + 1;
            if(ans < mid){
                ans = mid;
            }
        } else {
            high = mid - 1;
        }
    }
    cout << ans << '\n';
    return 0;
}