[백준 1654] 랜선 자르기

문제

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

1654번: 랜선 자르기

 

 

문제 분석 

잘라서 가져야하는 랜선의 개수가 주어지고, 가지고 있는 랜선의 길이가 주어진다. 

 

랜선을 잘라 개수를 맞추는데 최대한 길게 남겨두고, 또 같은 길이로 자른다면 몇 m로 잘라야 하는지 구하는 문제이다. 

 

 

알고리즘 설계 

우선 얻어야하는 랜선의 개수를 정수형 변수 n으로, 랜선들의 길이를 담을 vector vec을 전역변수로 선언한다.

 

main함수에서 몇개의 랜선을 입력받을지 정하는 loop와 랜선의 각각 길이를 입력 받을 input을 정수형 변수로 선언한다. 

이후 loop와 n을 입력 받아, 랜선의 개수와 얻어야하는 개수를 입력한다. 

 

loop의 개수대로 반복문을 돌리고, input으로 입력 받은 값을 vec에 넣어준다. 

 

vec을 sort함수를 사용하여 정렬하고, 매개변수 탐색을 위한 BinarySearch함수를 만들고, 반환되는 값을 출력한다. 

 

BinarySearch안에서 unsigned long long 형태로 left, right, center, sum을 선언한다.

left엔 1을, right엔 vec의 마지막 값과 n을 곱하여 넣어준다. 

 

left가 right보다 작거나 같을때 실행되는 while을 만들어주고, 

안에서 sum을 0으로, center을 left와 right를 더한 값에 반 값을 넣어준다. 

범위 기반 for에 vec을 넣고, i를 빼주고, i / center값을 sum에 더해준다/ 

범위기반 for가 끝나고 sum이 n과 같거나 크다면 left를 center에 1을 더한 값을, 아니라면 right에 center에 1을 뺀 값을 넣어준다. 

 

마지막으로 right를 반환해준다. 

 

 

유의점

이분탐색과 매개변수 탐색의 사전 지식이 필요하다. 

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int BinarySearch();

int n;
vector<int> vec;

int main()
{
    int loop, input;

    cin >> loop >> n;
    while(loop--)
    {
        cin >> input;
        vec.push_back(input);
    }

    sort(vec.begin(), vec.end());
    cout << BinarySearch();
}

int BinarySearch()
{
    unsigned long long left = 1, right = vec.back() * n, center, sum;

    while (left <= right)
    {
        sum = 0;
        center = (left + right) / 2;
        for (auto i : vec)
            sum += i / center;

        if (sum >= n)
            left = center + 1;
        else
            right = center - 1;
    }

    return right;
}