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

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

1654번: 랜선 자르기

소스 코드 :

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

int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);
	int K, N;
    int result = 0;
	vector<long long int> v;
	cin >> K >> N;
	for (int i = 0;i < K;i++)
	{
		long long int element;
		cin >> element;
		v.push_back(element);
	}
    sort(v.begin(), v.end());
    long long int start = 1;
    long long int end = v[K-1];
    long long int mid;

    while (start <= end)
    {
        long long int sum = 0;
        mid = (start + end) / 2;

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

        if (sum >= N)
        {
            start = mid + 1;
            if (result < mid)
                result = mid;
        }

        else if (sum < N)
            end = mid - 1;
    }
	cout << result;
}

마무리 : 입력값이 매우 크기 때문에 자료형을 long long int로 하였다. 그리고 최대한 많은 랜선을 구하기 위해서는 입력된 랜선값 내에서 구해야하기 때문에 이진 탐색으로 나누어서 최댓값을 구하면 된다.