Blog For Me

백준 1654번 랜선 자르기 본문

알고리즘 문제/백준

백준 1654번 랜선 자르기

PureStack 2021. 11. 19. 13:01

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

 

1654번: 랜선 자르기

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그

www.acmicpc.net

 

문제 풀이

  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;
}

'알고리즘 문제 > 백준' 카테고리의 다른 글

백준 1920번 수 찾기  (0) 2021.11.04
백준 10816 숫자 카드 2  (0) 2021.10.23
Comments