BOJ 1654(랜선 자르기)

📜 문제

문제링크
여러모로 배울게 많은 문제였다.

---

📖 풀이

문제의 조건을 읽어보면 K개의 랜선을 적당한 길이로 잘라서 N개의 랜선으로 만들때 최대 랜선의 길이를 구해야 한다. 단순하게 1 ~ MAX(K) 의 길이를 모두 확인해보면 O(MAX(K)^2) 의 시간복잡도로 문제를 해결할 수 있다. 하지만 문제에서 랜선의 최대 길이는 2^31 -1 이기 때문에 시간초과가 발생하게 된다. 따라서 O(N) 정도의 시간복잡도를 갖도록 문제 풀이를 변경해야 한다.

1. 공간복잡도

   1) K개의 랜선을 저장할 vector

K는 1 x 10^4 개 이하이므로 해당 문제에서 메모리 제한을 걱정할 필요는 없다.

2. 시간복잡도

   1) K 개의 랜선 길이 오름차순 정렬 O(K*log(K))
   2) 1 ~ MAX(K) 범위 탐색 O(log2(2^31))
   3) 랜선 개수 count O(K)

1 ~ MAX(K) 범위를 이분탐색을 통해 O(log2(2^31)) 의 시간복잡도로 자를 랜선의 길이를 선택하고 해당 길이를 통해 몇 개의 랜선을 가질 수 있는지 count 하기 때문에 총 시간 복잡도는 O(log2(2^31)) x O(K) 로 시간내에 해결할 수 있다.

---

🖥 코드

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

int k, n;
long long answer;
vector <long long> Lan;

long long count_lan(long long min_value){
    int cnt = 0;
    for(int i = 0; i < Lan.size(); i++){
        long long cut_lan = Lan[i] / min_value;
        cnt += cut_lan;
    }
    return cnt;
}

int main(void){

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> k >> n;
    for(int i = 0; i < k; i++){
        int number;
        cin >> number;
        Lan.push_back(number);
    }
    sort(Lan.begin(), Lan.end());

    long long start = 1, end = Lan[k-1];
    while(start <= end){
        long long mid = (start + end) / 2;
        long long cnt = count_lan(mid);
        // n개의 랜선을 만들지 못할 경우, 더 적은 길이로 잘라야 한다.
        if(cnt < n) end = mid - 1;
        else{
            if(mid >= answer)answer = mid;
            start = mid + 1;
        }
        
    }
    cout << answer;
    return 0;
}

---

🔨 피드백

처음 문제를 읽고 제한시간 내 통과를 위해 이분탐색 풀이를 떠올리는데 까지는 별로 시간이 걸리지 않았다. 하지만 크게 2 가지 실수를 해서 AC 를 받는데 까지 시간이 오래 걸렸다.

1) 가장 짧은 랜선을 사용하지 않을 수도 있다.

처음 문제를 접근할 때 가져온 K개의 랜선중에서 가장 짧은 랜선을 무조건 사용한다고 생각하고, 1 ~ MAX(K) 의 범위가 아닌 1 ~ MIN(K) 의 범위에서 탐색을 진행했다.

3 6
40
20
2
//정답 : 10

그렇게 되면 위와 같은 테스트 케이스를 통과할 수 없게 된다. 따라서 MAX(K) 까지의 모든 case를 탐색해야 한다.

2) long long 자료형을 사용해야 한다.

문제의 조건에 랜선의 길이는 2^31 - 1 이하라고 명시되어 있기 때문에 int 를 사용해서 탐색을 진행할 수 있을거라 생각했다. 하지만 K개의 랜선 중 최대값이 2^31 -1 인 경우,
이분탐색을 진행할 때 int mid = (start + end) / 2; 연산을 진행하기 때문에
start = 1, end = 2^31 -1 이기 때문에 mid는 integer overflow 가 발생하게 된다.

1 1
2147483647
//정답: 2147483647

🔥이분탐색 문제도 많이 풀어봐야겠다!