[1654] 랜선 자르기

---

 

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

1654번: 랜선 자르기

 

 

🔎 해결 방법 

[2110] 공유기 설치와 정말 정말 유사한 문제이다. 코드도 거의 복붙 수준 ㅋㅋ

1. left = 1, right = (가장 긴 랜선의 길이)로 선언

2. left <= right 동안 make 함수를 돌면서 만들 수 있는 랜선의 개수가 n보다 크거나 같으면 더 크게 잘라도 가능할 수 있다는 소리이므로 left = mid + 1로 업데이트!

하지만 랜선의 개수가 n보다 작다면 길이를 좀 더 작게해서 잘라야 한다는 소리이므로 length 값이 작아져야 한다.

따라서 right = mid - 1로 업데이트!

 

check 함수는 그냥 내가 자르고자 하는 랜선의 길이가 length 일 때 총 몇개의 조각이 나오는지만 판단해서 반환해주는 역할을 한다. 

이 문제의 핵심 포인트는 left, right, mid, answer 모두 long long 형으로 선언해주어야 한다는 점!!!

내가 가진 조각의 개수는 최대 10,000개이고 각각의 길이가 모두 2^31 - 1 인데 이 랜선 모두를 1cm로 자른다고 하면

총 10,000 x (2^31 - 1)개의 랜선이 생기기 때문에 int 형으로 하면 시간초과가 뜬다.

 

 

💡 내 코드(C++)

// [1654] 랜선 자르기
// https://www.acmicpc.net/problem/1654
// 이분 탐색
/* 랜선이 10,000개이고 모두 1cm로 자르면 10,000x(2^31-1) 조각이 나옴
  -> left, right, mid, answer 모두 long long 타입으로 선언!! */ 

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

int check(vector<int> &lan, int k, int n);
int make(vector<int> &lan, int k, int length);

int main(void)
{
    int k, n; // 오영식이 이미 가지고 있는 랜선의 개수, 필요한 랜선의 개수
    scanf("%d %d", &k, &n);
    vector<int> lan(k);
    for (int i = 0; i < k; i++) {
        scanf("%d", &lan[i]);
    }
    sort(lan.begin(), lan.end());
    printf("%d\n", check(lan, k, n));
}

int check(vector<int> &lan, int k, int n)
{
    long long left = 1;
    long long right = lan[k - 1];
    long long answer = 0;
    while (left <= right) {
        long long mid = (left + right) / 2;
        if (make(lan, k, mid) >= n) {
            left = mid + 1;
            answer = mid;
        }
        else {
            right = mid - 1;
        }
    }
    return answer;
}

int make(vector<int> &lan, int k, int length)
{
    int cnt = 0;
    for (int i = 0; i < k; i++) {
        cnt += lan[i] / length;
    }
    return cnt;
}