[ BOJ 1654 ] 랜선 자르기(Python)

문제

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

이미 가지고 있는 k개의 랜선으로 n개 이상의 랜선을 만들어야 한다.
이때 만들 수 있는 랜선의 최대 길이를 구하는 문제다.
mid 값이 0 이 나올 수 있다는 점을 고려 못해서 한참 헤맸다.

문제 풀이

1. 배열의 범위 정하기

l, r = 1, max(lans)

2. 중간값 mid 구하기

• mid로 랜선의 길이를 나눈 몫을 이용하기 위해
  값이 0일 땐, 1로 할당해주었다.

mid = ((l + r) // 2 if (l + r) // 2 !=0 else 1)

3. 랜선의 개수 세어주기

check = sum( l // mid if l >= mid else 0 for l in lans)

랜선을 mid 값으로 잘랐을 때, 나올 수 있는 랜선의 개수를 check 변수에 넣어주었다.

• 이때 랜선의 길이가 mid 보다 작으면, 자를 수 없으므로 원래 랜선의 길이를 넣어주었다.

4. 랜선의 개수가 m개와 같거나 m개보다 많을 경우
   4-1. 랜선의 개수를 result 변수에 할당해주었다.
   4-2. l을 mid + 1로 할당해주었다.
   (l의 값이 커진다 = mid 값이 증가한다 = 랜선의 개수가 감소한다)
5. 랜선의 개수가 m개보다 작을 경우
   5-1. r을 mid - 1로 할당해준다.
   (r의 값이 작아진다 = mid 값이 감소한다 = 랜선의 개수가 증가한다)

코드

import sys
input = sys.stdin.readline

# 이미 가지고 있는 k개의 랜선, n개의 랜선 필요
# n개(또는 n개보다 많이) 를 만들 수 있는 랜선의 최대 길이

k, n = map(int,input().rsplit())
lans = []
for _ in range(k):
    lans.append(int(input()))

l, r = 1, max(lans)
result = 0

while l <= r:
    mid = ((l + r) // 2 if (l + r) // 2 !=0 else 1)
    check = sum(l // mid if l >= mid else 0 for l in lans)
    print("check:{0}, mid:{1}, l:{2}, r:{3}".format(check,mid,l,r))
    if check >= n:
        l = mid + 1
        result = max(result, mid)
    else:
        r = mid - 1

print(result)