[백준] 랜선 자르기

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

1654번: 랜선 자르기

 

발상에 도움이 된 영상: https://www.youtube.com/watch?v=94RC-DsGMLo 

---

문제 설명

 기존에 있던 랜선 K개를 동일한 양의 정수 길이 L 단위로 잘라 N개 이상의 동일한 랜선을 얻을 때, L의 최대값을 구하는 문제다. 일단 L의 후보 L'을 찾으면  ∑ ( Ki // L' )  >= N인지 판단할 수 있는데, 해당 조건을 만족하는 경우 L'을 현재 최대값으로 삼는다. 이후 이진 탐색을 통해 L'이 계속 커지는 방향으로 탐색하여 더 이상 탐색할 수 없으면 최대 값을 발견한게 된다. L'에 대해 이진 탐색을 수행한다는 발상만 있다면 어렵지 않은 것 같다.

주요 논리

• left = 1
• right = max(K)

 자르는 길이 L은 left와 right 사이에 존재한다. 현재 문제에서 주의할 점은 L이 양의 정수인 길이라는 점이다. 양의 정수의 최소값은 1이므로 left = 1로 지정하여 Ki에 대해 몫을 구할 때 Division By Zero가 발생하지 않게 주의하자.

1. ∑ ( Ki // L' )  < N: L'의 길이가 너무 긴 상태이므로 right = mid - 1로 설정한다.
2. ∑ ( Ki // L' )  >= N: L'의 길이가 충분히 짧다. left = mid + 1로 설정하여 더 큰 L'이 가능한지 탐색해본다.

2번 코드에 의해 L'은 항상 기존의 값보다 더 커진다. 따라서 L'을 비교하는 코드는 필요하지 않다.

위와 같은 논리를 적용한 코드는 다음과 같다.

from sys import stdin
input = stdin.readline
K, N = map(int, input().split(' '))
lines = [int(input()) for _ in range(K)]
ml = max(lines) # 랜선의 최대 길이

left = 1 # 자르는 길이를 0으로 할 수는 없음
right = ml

result = 0

while left <= right:
    Lp = (left + right) // 2 # 자르는 위치
    count = 0 # 길이 최대
    for line in lines:
        count += line // Lp
    
    if count >= N:
        left = Lp + 1
        result = Lp
    else:
        right = Lp - 1
print(result)

 위에서 설명한 L은 result에 대응된다. 각 랜선을 길이 Lp 단위로 잘라서 개수 count을 센다. 만약 count가 사용자가 원하는 개수 N보다 크거나 같은 경우 L을 더 크게 만들 수 있는지 탐색하기 위해 left = Lp + 1로 지정한다. 반대의 경우 현재 Lp의 길이가 너무 긴 상황이기 때문에 right = Lp - 1로 지정하여 탐색 범위의 값을 낮춘다.

---

 위 내용과는 별개로 input이 정말 느리다는게 체감됬다. input을 이용하여 답을 맞춘 다음 답안을 보는데, 다른 사람에 비해 너무 시간이 오래 걸렸다. 혹시 로직이 문제인가 싶어 코드를 봤는데 로직은 완전히 동일하고 input과 sys.readline 만 달랐다. 시간 차이가 5배 이상 나는걸 보면 다음부터는 의도적으로 readline을 사용해야겠다.

발생한 시간 차이