[백준] 1654 랜선 자르기 (Baekjoon Problem 1654: Cut LAN Cable)

문제 출처

 

[문제 요약]

길이가 제각각인 랜선 k개가 주어진다.

이를 길이가 동일한 n개의 랜선으로 잘라야 할때 가장 크게 자를 수 있는 길이를 출력하면 된다.

 

* 자를때 손실되는 길이 없음

** 기존 주어진 k개의 랜선으로 n개의 랜선을 만들 수 없는 경우는 없다고 가정 (답이 항상 있다)

*** 단위는 정수

[풀이]

이분 탐색 문제이다.

간단하게 1부터 아직 어딘지 모를 최대 길이 limit가 있다고 가정을 하자.

 

설명에는 편의상 소문자로 적겠다.

보통 수열에서의 이분탐색은 범위를 가리키는 시작점(start)과 끝점(end)가 있고 찾아야 하는 수 정답(ans)이 있다면

start와 end의 딱 절반 지점인(이 문제에서는 중앙값인) half가 ans보다 큰지 작은지를 비교하면서 점점 그 범위를 좁혀 나가는 방식이다.

 

//은 integer division(몫)이다.

half가 ans보다 작으면 end를 half라고 하고

half가 ans보다 크면 start를 half라고 다시 정의를 하고

 

새로운 start와 end에서 half를 찾아나가 정답을 찾을 때 까지 범위를 좁히면 된다.

 

이 문제에서 정의하면 되는건

limit와 정답의 조건이다.

 

우선 limit는 간단하다. 정답이 될 길이(ans)은 모든 k개 랜선들의 합을 n으로 나눈 값보다는 클 수 없다.

따라서 limit는 아래처럼 정의 할 수 있다.

정답이 되는 조건은 각각의 랜선을 half로 나누어 나온 선의 개수를 모두 합한 값(sum)이 n보다 같거나 큰지를 보면 된다.

 

sum of cables // half > n일 경우 start = half

sum of cables // half < n일 경우 end - 1 = half

 

이를 확인하는 함수(works)는 아래처럼 간단히 만들 수 있다.

def works(lst:int, k, n):
    rope_num = 0
    for knot in lst:
        rope_num += knot//k

    if rope_num >= n:
        return 1
    else:
        return 0

하나 만들어 아까 half를 확인하는 조건에 그대로 적용시켜주자.

[유의할 점]

문제를 풀때는 list가 아닌 start, end만 가지고 풀자.

처음에 수를 list로 정의했더니 메모리 초과가 떴다.

 

룹(loop)에서 나오는 순간을 start == end인 경우로 했지만

integer division을 쓰다보니 문제에서 주어진 예시 같은 경우 start = 199, end = 200이어서 half가 199인채로 계속 룹을 도는걸 확인했다. 

그래서 prev_k라는 변수를 하나 더 만들어 이전 변수와 같은 중앙값을 가지는 조건을 추가로 만족해도 룹을 나오게 했다.

(사실상 whilte True로 돌리는게 확인하는 비용이 줄어 더 빠를거 같긴하다)

 

그리고 룹을 나왔을때 half말고 end값이 만족하는 경우가 많기에

한번 더 조건을 만족하는지 확인을 해주고 만족하면 end를, 아니면 start를 돌려준다.

여기서 works함수로 체크하는 이유는 start만 계속 바뀌어서 end가 (아래 코드상 k-1로 assign 된적이 없으면) works를 만족하지 않는 경우도 있기 때문이다

[파이썬 3 코드]

# -*- coding: utf-8 -*-

def works(lst:int, k, n):
    rope_num = 0
    for knot in lst:
        rope_num += knot//k

    if rope_num >= n:
        return 1
    else:
        return 0


def find_maxlen(lst, lim, n):
    start = 1
    end = lim

    prev_k = 0
    while start != end:
        k = (start + end)//2
        if prev_k == k:
            break
        if works(lst, k, n):
            start = k
        else:
            end = k - 1
        prev_k = k

    if works(lst, end, n):
        return end
    else:
        return start


if __name__ == "__main__":
    k, n = map(int, input().split())

    lens = []
    sum = 0
    for i in range(k):
        lens.append(int(input()))
        sum += lens[-1]

    limit = sum // n

    ans = find_maxlen(lens, limit, n)
    print(ans)