백준 1654 - 랜선 자르기 - 이분 탐색

문제

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

풀이전략

1. 우리가 구할 랜선의 최대 길이를 이분 탐색으로 구해준다.
2. 선택한 각 길이마다 따로 getNumberOfLine이라는 함수를 만들어 해당 길이로 몇개를 만들 수 있는지 구해야한다.
3. 개수가 같거나 더 많다면 길이를 늘려주고 적다면 길이를 줄여야한다.

코드

#include<bits/stdc++.h>

using namespace std;

int N, K;
vector<int> a;

//// 문제에서 lt, rt, 그리고 최대값 m까지 long long으로 받아야 답이 해결된다.
//// 바보같이 최대값이 2147000000이지만 이는 2^32보다 작은값이다... 하지만 문제에서 mid를 계산할때
//// int형의 범위를 넘어버린다. 따라서 lt와 rt도 long long으로 해주어야한다 . 

long long getNumberOfLine(int num, int length){
    long long cnt = 0;
    // 0보다 크다가 아니라 크거나 같다이다.... 여기서 문제 틀림
    while(num-length >= 0){
        cnt++;
        num = num-length;
    }
    return cnt;
}
int res = 0;
int BinarySearch(long long lt, long long rt){
    if(lt > rt){
        return res;
    }
    else{
        
        long long mid = (lt+rt) / 2;

        long long numOfLine = 0;
        for(int i=0; i<N; i++){
            numOfLine += getNumberOfLine(a[i], mid);
        }

        /// 항상 정확히 필요한 부분까지만 하면 되는거라고 생각했지만 N개보다 더 많이 만드는것도 N개를 만드는것에 포함된다. 
        if(numOfLine >= K){
            if(mid > res){
                
                res = mid;
            }
            return BinarySearch(mid+1, rt);
        }
        else {
            return BinarySearch(lt, mid-1);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);

    cin >> N >> K;
    int tmp;
    int m = 0;
    for(int i=0; i<N; i++){
        cin >> tmp;
        a.push_back(tmp);
        if(tmp > m ) m = tmp;
    }

    cout<<BinarySearch(1, m) << endl;
    return 0;
}

소감

문제의 핵심아이디어는 알았지만 중간중간에 실수가 너무 잦아서 조금 헤매었다. 먼저 항상 long long을 써야할때는 확실하게 써줘야한다. 이를 실수하는 문제가 뒤에도 많다... 반드시 long long을 써줄 때는 써줘야한다. 또한 매우 중요한 부분이 있었는데 numOfLine >= K 일때 res값을 바꿔줘야한다. 나는 처음에 numOfLine == K 일때만 바꿔줬는데 인풋에 따라 해당조건에서 답을 구할수 없을 수 있다. 즉 K==3인데 numOfLine이 4로만 나올때가 있기 때문이다.

이번문제에서 많이 배웠다.
1. long long
2. numOfLine >= K