[백준 1654번] 랜선 자르기 (C/C++)

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

---

랜선 자르기 문제는 K가 10,000이하이고, N이 1,000,000 이하이므로, 전체를 탐색하면 시간이 초과되기 때문에 이분탐색을 이용해야합니다. 

또한 랜선의 길이는 int형의 최대값이 될 수 있으므로, 아래 케이스의 경우 만들 수 있는 랜선의 개수는 int형의 범위를 벗어날 수 있습니다. 따라서 자료형으로 long long형을 사용해야합니다. 

2 1000
2147483647
2147483647

 

아래의 cut()함수는 길이가 length일 때, 만들 수 있는 랜선의 개수를 반환하는 함수입니다. 

long long cut(long long length){ // 길이가 length일 때, 만들 수 있는 랜선의 개수를 반환하는 함수
    long long cnt = 0;
    for(int i = 0; i < k; i++)
        cnt += arr[i] / length;
    return cnt;
}

 

N개보다 많이 만드는 것도 N개를 만드는 것에 포함되며, 만들 수 있는 랜선의 최대 길이를 출력해야하므로, 이분탐색의 탈출 조건은 cut(length) >= n이고 cut(length + 1) < n이 되어야합니다.

하지만, cut(length) >= n이면서 cut(length + 1) >= n이 될 수 있습니다. 이 경우 length가 n개의 랜선을 만들 수 있는 최대 길이가 아니므로 length의 값을 더 증가시켜 탐색을 진행해야합니다. 따라서 두 번째 else if 문의 조건이 cnt > n이 아닌 cnt >= n이 되어야 합니다.

 

아래는 전체 코드입니다.

high와 low가 모두 int형일 경우, (high + low)의 결과로 오버플로우가 발생할 수 있으므로, high와 low 모두 long long형으로 정의했습니다. 또한 길이가 length일 때, 만들 수 있는 랜선의 개수를 반환하는 함수 또한 반환형이 long long이 되어야 합니다. 

#include <bits/stdc++.h>
using namespace std;

int arr[1000000];
int k, n;

long long cut(long long length){ // 길이가 length일 때, 만들 수 있는 랜선의 개수를 반환하는 함수
    long long cnt = 0;
    for(int i = 0; i < k; i++)
        cnt += arr[i] / length;
    return cnt;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> k >> n;

    for(int i = 0; i < k; i++) cin >> arr[i];

	// high, low의 범위 설정, 랜선을 자를 수 있는 최대 길이는, 입력된 랜선들 중 최대 길이
    long long high = *max_element(arr, arr + n); 
    long long low = 1;	// 최소 길이는 1

    while(high > low){	// 이분탐색 수행
        long long length = (high + low) / 2;
        long long cnt = cut(length);
        
        if(cnt >= n && cut(length + 1) < n){
            break;
        }else if(cnt >= n){  
            low = length + 1;
        }else if(cnt < n){
            high = length - 1;
        }
    }
    cout << (high + low) / 2;
}

 

아래는 문제 풀이에 사용된 테스트 케이스입니다.

2 1000
2147483647
2147483647

1 1
802

4 4
1
1
1
1