[백준 c++] 14627 파닭파닭

문제

https://www.acmicpc.net/problem/14627
파의 개수 S, 닭의 개수 C, S줄에 걸쳐 파의 길이가 입력으로 주어진다.
닭 한마리에는 하나의 파만 넣을 수 있다. 여러 파를 잘라서 한 닭에 넣을 수 없다는 뜻이다.
파의 양을 최대한 많이 넣으려고할 때 사용하고 남은 파의 양을 구하는 문제다.

풀이

조건을 만족하는 파의 양을 찾는 문제다.
특정 값을 찾는 문제로 이진탐색을 이용하여 풀 수 있다.
파의 길이 범위(1 ≤ L ≤ 1,000,000,000)를 생각해서 long long으로 풀어줘야한다.

mid로 모든 파를 나눴을 때 몫의 총합이 만들어야할 닭의 양보다 적다면, 파를 더 잘게 썰어야하므로 high = mid-1, 아니라면 low = mid+1

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, m;
long long sum, res;
int main()
{
    cin >> n >> m;
    vector<int> v(n);
    int lo = 1, hi = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> v[i];
        hi = max(hi, v[i]);
        sum += v[i];
    }

    while (lo <= hi)
    {
        long long mid = (lo + hi) / 2;
        int cnt = 0;
        for (int i = 0; i < n; i++)
        {
            cnt += (v[i] / mid);
        }
        if (cnt < m)
            hi = mid - 1;
        else
        {
            lo = mid + 1;
            res = mid;
        }
    }
    cout << sum - (res * m) << "\n";

    return 0;
}