백준 1654 - 랜선 자르기

1. 문제 정리
  - N과 K를 입력 받는다.

  - K개의 랜선을 잘랐을 때, N개의 랜선을 만드는 가장 긴 길이의 랜선을 구한다.

  - N개 이상의 랜선 또한 답에 포함한다.(Upper Bound)
 
2. 접근
  - 언뜻 배열이 아니라 그냥 브루트 포스로 풀 수도 있지만, 보면 이분탐색으로 충분히 풀 수 있는 문제이다.\

  - 정답을 가정한 값으로 위 조건(N개 이상의 랜선)을 충족하는 지 짚어갈 것이다.
 
3. 풀이

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

long n, k;
long lo = 1;
long hi;
long ans = 0;
vector<long> lan;

void bis(){
    while(lo <= hi){
        long mid = (lo + hi) / 2;
        long cnt = 0;
        for(int i: lan){
            cnt += i/mid;
        }
        if(cnt < n) hi = mid-1;
        else {
            lo = mid+1;
            if(ans < mid) ans = mid;
        }
    }
}

int main(){
    cin >> k >> n;

    for(int i = 0; i < k; i++){
        long input;
        cin >> input;
        lan.push_back(input);
        if(hi < input) hi = input;
    }
    bis();
    cout << ans;
}

  - int lo, hi : 이분탐색의 left와 right값으로 보면 되겠다.

  - void bis() : i/mid 에서 mid 가 0이 되는 것을 방지하기 위해 lo값을 1로 설정해둔다. 이후 이분탐색을 진행한다.

 
4. 소감

  처음 풀어보는 이분탐색 문제였다. 이전에 풀었던 그래프, DP, 입출력, 정렬, 트리 문제 등은 강의를 듣고 시작을 해서 큰 무리 없이 시작을 할 수는 있었지만, 이번 이분탐색은 학교 전공 수업 때 들었던 자료구조, 알고리즘 수업 외에 처음으로 접하는 거라 좀 낯설게 느껴졌다.

  앞으로는 한동안 이분 탐색 문제들을 접해가면서 익숙해져가는 것을 목표로 해야겠다.