[BOJ] 백준 1654. 랜선 자르기

▶문제설명

[BOJ] 백준 1654. 랜선 자르기

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

▶ 설계

---

현재 K개의 랜선이 있는데 가지고 있는 랜선들을 일정한 길이로 잘라서 N개의 랜선으로 만들어야한다.

랜선을 N개 이상으로 만들 수 있는 랜선 길이의 최대값을 구하는 문제이다.

랜선 길이 len을 먼저 정하고 해당 길이로 N개 이상의 랜선을 만들 수 있는지 판단하는 방식으로 문제를 해결할 수 있을 것으로 보인다.

len의 길이는 이분탐색으로 값을 정해주면 빠른 시간에 문제를 해결할 수 있게 된다.

left는 가능한 랜선 길이의 최소값,

right는 가능한 랜선 길이의 최대값으로 초기화 한다.

그리고 (left+right)/2에 해당하는 mid 값으로 N개 이상의 랜선을 만들 수 있는지 판단하면서 가능한 랜선 길이의 최대값을 구하면 된다.

▶ 구현

---

우선 메인문을 작성하자.

int main(){
    cin >> K >> N;
    long long left, right;
    left = 1;
    right= 0;
    for(int i=0; i<K; i++){
        cin>>lan[i];
        if(right < lan[i])
            right = lan[i];
    }
 
    return 0;
}

랜선의 길이가 2^31-1보다 작거나 같다고 했으므로

left와 right 값을 long long으로 처리해줘야 오버플로가 발생하지 않는다.

가능한 랜선의 길이 중 최대값은 입력으로 주어진 랜선의 길이 중에 최대값이므로 입력을 받으면서 구해주었고

가능한 랜선의 길이 중 최소값은 1로 초기화해주었다.

int main(){
    cin >> K >> N;
    long long left, right;
    left = 1;
    right= 0;
    for(int i=0; i<K; i++){
        cin>>lan[i];
        if(right < lan[i])
            right = lan[i];
    }
 
    long long ans = 0;
    while(left<=right){
        long long mid = (left+right)/2;
        if(check(mid)){
            right = mid-1;
        }
        else{
            ans = mid;
            left = mid+1;
        }
    }
    cout<<ans<<endl;
    return 0;
}

이분탐색으로 가능한 랜선의 길이 중 최대값을 찾는 문제이다.

check 함수는 mid 값으로 만들어지는 랜선의 개수가 N 미만인지를 판단하여 T/F를 반환해준다. (line 15)

정해진 랜선의 길이(mid)가 길어서 N개 미만의 랜선이 만들어지는 경우에 

mid 값을 줄여주어야 다음 루프에서 만들어지는 랜선의 개수를 높일 수 있으므로 right 값을 mid-1로 바꾼다. (line 16)

정해진 랜선의 길이(mid)가 짧아서 N개 이상의 랜선이 만들어지는 경우에 

mid 값을 높여주어야 다음 루프에서 만들어지는 랜선의 개수를 높일 수 있으므로 left 값을 mid+1로 바꾼다. (line 20)

랜선의 길이를 mid로 하면 N개 이상의 랜선이 만들어지므로 ans 값을 mid로 갱신한다. (line 19)

left 값이 right 값보다 커지는 경우에 이분 탐색을 종료하도록 구현하면 N개 이상의 랜선을 만들 수 있는 랜선 길이의 최대값이 ans에 담기게 된다.

핵심이 되는 부분인 check 함수를 구현해보자.

bool check(long long length){
    long long numLan = 0;
    for(int i=0; i<K; i++)
        numLan += lan[i]/length;
    return numLan < N;
}

매개변수로 받은 length 길이로 만들어진 랜선의 개수를 나타내는 numLan을 구한다. (line 4)

가지고 있는 랜선을 length로 나눈 몫이 length 길이의 랜선을 몇 개 만들 수 있는지를 나타내므로

lan[i]/length를 누적해주면 된다.

numLan이 N 미만이면 true, 이상이면 true를 반환하도록 구현했다.

▶ 결과

---

▶Solution

---

[소스코드 보기]