[백준/이분탐색/C++] 1654번 랜선 자르기

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

1654번: 랜선 자르기

문제풀이 방법

• 길이는 int 형의 범위를 넘어가기 때문에 long long int 형으로 선언해준다 (개수는 상관없음)
• 문제에서

예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)

의 예시를 보면, 만들어지는 랜선의 개수를 셀 때 랜선의 길이를 빼는것이 아니라 나눈 몫을 더해주어야 한다

• 나누어주는 값이 0이 아니게하는 조건을 추가한다

#include <bits/stdc++.h>

using namespace std;

int k, n;
vector<int> v;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> k >> n;

    int start = 1;
    long long int end = 0;

    for (int i = 0; i < k; i++) {
        int x;
        cin >> x;
        if (x > end) end = x;
        v.push_back(x);
    }
    sort(v.begin(), v.end());

    int total = 0; // 만들 수 있는 개수
    long long int result = 0; // 최대 길이 저장
    long long int mid = 0; // 자르는 길이

    while (start <= end) {
        total = 0;
        mid = (start + end) / 2;
        if(mid == 0) break;

        for (int i = 0; i < k; i++) {
            total = total + v[i] / mid;
        }

        if (total < n) end = mid - 1; // 만들어진 개수가 작을 경우
        else { // 만들어진 개수가 충족된 경우
            result = mid;
            start = mid + 1;
        }
    }
    cout << result <<'\n';

    return 0;
}