[Baekjoon]백준 1654 랜선 자르기(실버 2) - Python, C++

문제설명

문제를 읽어보면 영식이는 여러 개의 랜선을 가진 상태에서 N개의 랜선을 만들고싶어한다

그리고 N개 이상의 랜선을 만들 수 있는 가장 긴 랜선의 길이를 구하는 것이 문제이다

예제를 보면 802, 743, 457, 539 이렇게 3개가 존재하는데

랜선 하나의 길이가 201이 되면 11개를 만들 수 없지만, 200이 된다면 11개를 만들 수 있게 된다

 

그래서 처음에 들었던 생각으로는 모든 길이를 합친 후에 여기서 수를 나누어가며 확인해야되나? 라고 생각했다

예제에서의 상황으로 가정하면 모든 수를 더하게 되면 2541이 나오게 되고, 이를 11로 나누면 231이 된다

이 231을 이용하여 수를 조절하며 확인을 해볼까..? 라는 생각을 잠깐 해보다가 만약 숫자들의 차이가 너무 커지면

시간복잡도 측면에서 너무 불리할 것 같다는 생각이 들었다

 

그래서 다음으로 생각해낸 방식이 해당 랜선들 중에서 가장 긴 길이와 1을 기준으로 이분탐색을 사용하는 것이었다

이 중간지점을 계속해서 갱신하면서 목표 개수 이상의 랜선을 만들 수 있는 경우의 수를 구하는 것이다

예제를 예시로 들어 설명하자면 1, 802를 기준으로 mid는 401로 설정한다 이후 401로 각 랜선을 잘랐을 때

총 몇개의 랜선이 나오는지 확인한 후에 만약 목표치보다 작다면 mid가 크다는 뜻이므로 mid = end - 1로 설정하고

반대로 목표치보다 크다면 mid가 작다는 뜻이 되기 때문에 mid = start + 1로 설정하면 된다

이를 end보다 start가 더 커질때까지 반복하면 된다 그리고 start가 더 커지는 그 순간의 end값이 최대 길이이므로

print(end)를 하면 정답을 확인할 수 있다

LAN, num = map(int, input().split())
LAN_length = []
for _ in range(LAN):
    LAN_length.append(int(input()))

start, end = 1, max(LAN_length)
while start <= end:
    mid = (start + end) // 2
    cnt = 0
    for ln in LAN_length:
        cnt += ln // mid
    if cnt >= num: # 목표치보다 더 많은 랜선이 만들어지는 경우
        start = mid + 1
    else: # 목표치보다 더 작은 랜선이 만들어지는 경우
        end = mid - 1
        
print(end)

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

int main() {
    int LAN, num;
    cin >> LAN >> num;

    vector<int> LAN_length(LAN);
    for(int i = 0; i < LAN; i++) {
        cin >> LAN_length[i];
    }
    long long start = 1;
    long long end = *max_element(LAN_length.begin(), LAN_length.end());
    while(start <= end) {
        long long mid = (start + end) / 2;
        int cnt = 0;
        for(int i = 0; i < LAN; i++)
            cnt += LAN_length[i] / mid;
        
        if(cnt >= num)
            start = mid + 1;
        else
            end = mid - 1;
    }

    cout << end << endl;

    return 0;
}

C++로 작성할 때 주의점으로는 mid의 값을 구할 때 랜선의 길이끼리 더하는 과정이 존재하는데, 랜선의 길이가 

2^31 - 1이하이기 때문에 더하는 과정속에서 int 자료형의 범위를 넘길 수도 있다 따라서 start, end, mid는 

long long으로 설정하여야 틀렸습니다 라는 당황스러운 문구를 피할 수 있으니 주의해야한다