Baekjoon 1654번 랜선 자르기

문제

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

걸린 시간

00 : 55 : 23 실패

시간 초과 풀이

Python3

if __name__ == "__main__":
    # 랜선 자르기

    # 입력 : K, N
    K, N = map(int, input().split())

    # K 개의 랜선 길이를 담는 리스트
    lans = []

    for i in range(0, K):
        tmp = int(input())    
        lans.append(tmp)

    # K 개의 모든 랜선을 이었다 가정하고 자를때 N 개 이상의 랜선을 만들기 위한 최대 랜선 길이
    wLen = int(sum(lans) / N) # would length

    # K 개의 각 랜선을 mLan 에서 1씩 줄인 값으로 나누어 계산된 몫을 모두 더해 N 개 이상일 경우 멈추고 최대 길이로 설정한다. 
    mLen = 0 # max length
    quotient = []

    while True:
        for i in range(0, K):
            tmp = lans[i] // wLan 
            quotient.append(tmp)

        mLan = sum(quotient)

        if mLan >= N:
            break
        else:
            wLan -= 1

        quotient.clear()

    print(wLan)

처음 작성했던 풀이로 랜선 길이를 하나씩 줄이며 최대값을 찾는 알고리즘이다.

테스트 케이스의 랜선 길이(K) 값이 커지면 커질수록 상당히 오랜 시간이 걸린다.

옳은 풀이

Python3

if __name__ == "__main__":
    # 랜선 자르기

    # 입력 : K, N
    K, N = map(int, input().split())

    # K 개의 랜선 길이를 담는 리스트
    lans = []
    for i in range(0, K):
        tmp = int(input())    
        lans.append(tmp)

    # 파라메트릭 서치
    left, right = 1, max(lans)
    while left <= right:
        # left 와 right 의 중간
        mid = int((right + left) / 2)

        # quotient : 몫의 합
        quotient = 0

        # 모든 k 값을 랜선 길이(mid) 값으로 나눈 몫의 합 
        for i in range(0, K):
            quotient += lans[i] // mid

        # 몫의 합이 N 보다 크거나 같다면
        if quotient >= N:
            # mid 값을 결과로 저장
            result = mid    
            left = mid + 1
        else:
            right = mid - 1

    print(result)

Binary Search(이진 탐색; 이분 탐색)과 문제를 풀어나가는 과정이 매우 흡사한 Parametric Search(파라메트릭 서치) 방법을 이용한 풀이이다.

최대 랜선값이 포함되어 있는 범위는 편의상 최대 K 값으로 두어도 문제가 없다고 한다.

한가지 유의할 점은 나눗셈 연산에 mid 값이 사용된다는 점이다. ZeroDivisionError 런타임 에러가 일어나지 않도록 하려면 left 값을 0이 아닌 1으로 설정하면된다.

// 반례
1 1
1

C++

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm> // sort
using namespace std;

int K, N;

unsigned int binsearch(vector<unsigned int>& lans){
    unsigned int length, mid, ret;
    unsigned int left = 1;
    unsigned int right = lans[K-1];
    while(left <= right){
        length = 0;
        mid = (left+right)/2;
        for(int i = 0; i < K; i++)
            length += lans[i]/mid;
        // 결정 문제
        if(length >= N){
            ret = mid;
            left = mid+1;
        }
        else{
            right = mid-1;
        }
    }
    return ret;
}

int main(){
    scanf("%d %d", &K, &N);
    vector<unsigned int> lans(K);
    for(int i = 0; i < K; i++)
        scanf("%u", &lans[i]);
    sort(lans.begin(), lans.end());
    printf("%u\n", binsearch(lans));
    return 0;
}

파라메트릭 서치를 복습할 겸 다시 풀어보았는데 50% 쯤에서 틀렸습니다가 출력되었다.

원인은 이분 탐색의 mid 값 초기화에 있었다. left+right 에서 2³¹-1 을 초과하게 된다.

종만북 "자주하는 실수 - 너무 큰 중간 값" 에서도 언급되었던 실수이다.

출처

파라메트릭 서치(개념) - 주니어 개발자의 대나무숲