[백준 1654번/c++] 랜선 자르기

문제

 

---

구하고자 하는 것

K개의 랜선을 잘라 길이가 모두 같은 N개의 랜선을 만들 때, 만들 수 있는 최대 랜선의 길이

 

---

조건

• 랜선을 자르거나 만들 때 손실되는 길이는 없다.
• 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다.
• 항상 센티미터 단위로 정수길이만큼 자른다.
• N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다.

 

변수 범위

• K는 1이상 10,000 이하의 정수
• N은 1이상 1,000,000 이하의 정수
• 랜선의 길이는 2^31-1보다 작거나 같은 자연수

 

접근

길이 별로 몇 개의 랜선이 나오는지 확인하여야 한다.

 

모든 1부터 가장 긴 랜선의 길이까지 모두 탐색하면?

• 시간초과가 난다.
• O(가장 긴 랜선길이)
  • 가장 긴 랜선의 길이는 최대 2^31-1(약 20억)
• 그리고 랜선의 개수만큼 순회하며 총 몇 개가 만들어지는지 확인하므로 O(K)
• 시간초과 발생(1억에 1초)

따라서  O(log랜선길이)로 시간을 줄여줄 이분 탐색이 필요하다.

 

---

알고리즘

 

• 이분 탐색
• 매개 변수 탐색

 

---

풀이

이분탐색에서 쓰이는 변수

• lt, rt -> 데이터의 양 끝을 가리킨다.
  • lt가 왼쪽 끝, rt가 오른쪽 끝

1. 먼저 lt = 1, rt = 가지고 있는 랜선 중 가장 긴 랜선의 길이로 초기화 한다.

 

2. mid=(lt+rt)/2를 하고 각 랜선의 길이를 mid로 나누어 만들 수 있는 mid 길이의 랜선으로 만들 수 있는 랜선의 개수를 구한다.

• 랜선 K개 각각을 mid 길이로 나눈 몫을 다 더한다. 이 값을 cnt 라고 하자.

 

3. cnt의 값이 필요한 랜선의 개수 보다 같거나 크면

• 결과값이 저장될 변수 res에 mid를 대입하고
  • lt=mid+1을 하여 조건을 만족하는 더 긴 랜선의 길이를 찾는다.(오른쪽 끝인 rt는 그대로 두고 lt를 변경)

lt

mid

rt

 

lt

rt

 

• cnt의 값이 필요한 랜선의 개수 보다 작으면
  • rt=mid-1을 하여 필요한 랜선의 개수를 만족시키는 랜선의 길이를 찾는다.(왼쪽 끝인 lt는 그대로 두고 rt를 변경)

lt

mid

rt

 

lt

rt

 

• 이 과정은 lt<=rt인 동안 반복한다.

 

그러면 res는 필요한 랜선의 개수를 만들 수 있는 랜선의 최대 길이가 된다.

 

---

예제 손으로 직접 풀이

---

자료형 범위 주의

문제에서 랜선의 길이는 2^31-1보다 작거나 같은 자연수라고 제시되어 있다.

 

이렇게 되면 두 랜선의 길이를 더하여 2^31-1보다 커질 수 있다.

-> int형이 아닌 longlong형을 사용하여야 한다.

 

자료형	크기	범위
int	4바이트, 32비트	-(2^31-1) ~ 2^31-1
long long	8바이트, 64비트	-(2^63-1) ~ 2^63-1

 

 

---

성공코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int k, n;
vector<int> line;

int count(int len){
    int cnt=0;
    for(int i=0; i<k; i++){
        cnt+=line[i]/len;
    }
    return cnt;
}

int binarySearch(){
    long long mid, lt=1, rt, res;
    int max_line = *max_element(line.begin(), line.end());
    rt=max_line;
    while(lt<=rt){
        mid=(lt+rt)/2;
        if(count(mid)>=n){
            res=mid;
            lt=mid+1;
        } else{
            rt=mid-1;
        }
    }

    return res;
}

int main(){
    // freopen("input.txt", "rt", stdin);
    cin.tie(NULL);
    cout.tie(NULL);

    int line_len, res;
    cin >> k >> n;
    for(int i=0; i<k; i++){
        cin >> line_len;
        line.push_back(line_len);
    }
    cout << binarySearch();

    return 0;
}