[C++] 백준 1654 : 랜선 자르기

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

int K, N;
vector<int> line;

int main(int argc, char **argv){
    int x, maxN = 0;

    scanf("%d %d",&K,&N);

    for(int i=0; i<K; i++){
        scanf("%d", &x);
        line.push_back(x);
        maxN = max(maxN, x); // 최대값 저장
    }

    long long left = 1, mid, right = maxN;
    long long result = 0, tmp; // 초기화해주기
    while(left <= right){
        mid = (left + right) / 2;
        tmp = 0;
        for(int i=0; i<line.size(); i++){
            tmp += line[i] / mid;
        }

        if(tmp >= N){
            left = mid + 1;
            result = max(result, mid); // 값 갱신 - 랜선의 최대길이
        } else {
            right = mid - 1;
        }
    }

    printf("%lld", result);

    return 0;
}

원래는 이진 탐색으로 풀지 않고 중간값에서 -1씩 해주며 풀었다. 당연히 타임아웃... 그래서 이진 탐색을 통해 풀기로 하였다.

그리고 두 가지를 조심하기

• N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다.
  : 그러므로 N개 이상인 경우를 모두 구해준다.
• N개를 만들 수 있는 랜선의 최대 길이
  : 그러므로 랜선의 최대 길이를 갱신해가며 구해준 값에서 그 이상의 범위에서 이진 탐색을 계속해주어야한다.

그리고 result = 0으로 초기화해줘야한다! 안해줘서 값은 멀쩡히 출력이 되었는데 백준에 돌리니까 틀렸습니다가 나왔다.