백준 1654번 랜선 자르기

문제링크: https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

문제 풀이

1. 입력 받은 전선의 길이들을 오름차순으로 정렬한다.
2. 처음에 minWire 값을 1로 잡고, maxWire 값을 입력한 랜선 중 가장 긴 길이로 지정한다.
3. (minWire + maxWire) / 2 의 값을 midWire 변수에 대입하고, 각 길이를 mid 값으로 나누어 몇 개씩 전선을 만들 수 있는지 총합을 구한다.
4. 만약에 만들 수 있는 전선의 개수가 N보다 작으면, 가장 긴 길이인 maxWire의 값을 midWire - 1로 줄인다.
5. 반대로 만들 수 있는 전선의 개수가 N보다 크거나 같으면, 가장 짧은 길이인 minWire를 midWire + 1로 증가시키고, 최종 결과값을 갱신한다.
6. 가장 긴 길이를 출력한다.

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

vector<long long> wire;

int main()
{
        cin.tie(NULL);
        cout.tie(NULL);
        ios_base::sync_with_stdio(false);

        long long K, N;
        cin>>K>>N;

        for(int i=0;i<K;i++) {
                long long cen;
                cin>>cen;

                wire.push_back(cen);
        }

        sort(wire.begin(), wire.end()); // 전선의 길이 오름차순 정렬

        long long minWire = 1, maxWire = wire[wire.size()-1]; //가장 짧은 길이를 1로, 가장 긴 길이를 입력값 중 가장 큰 값으로 초기화
        long long result = 0;

        while(minWire <= maxWire) {

                long long midWire = (minWire + maxWire) / 2;

                int sum = 0;

                for(int i=0;i<K;i++) { // 만들 수 있는 전선의 개수를 구한다.
                        sum += wire[i] / midWire;
                }

                if(sum < N) { //조건 충족하지 못하면 가장 큰 값을 줄인다.
                        maxWire = midWire - 1;
                }
                else { //조건 충족했을 시 최종 결과값을 갱신하고 가장 작은 값을 증가시킨다.
                        result = max(result, midWire);
                        minWire = midWire + 1;
                }
        }

        cout<<result<<'\n'; //최종 결과값 출력
        return 0;
}