[Baekjoon] 1654번 : 랜선 자르기 (Python, 이분 탐색)

[Baekjoon] 1654번 : 랜선 자르기 (Python, 이분 탐색)

 

목차

 

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

1654번: 랜선 자르기

Python

 

방법 1 - 메모리 30860KB / 시간 488ms / 코드 길이 281B

 

K개의 랜선을 잘라 N개의 랜선을 만든다.

이때 가장 긴 길이의 랜선이 되도록 만드는 것이 포인트이다.

본 문제에 있어 난해했던 것은 과연 어떻게 하면 줄어드는 개수와 늘어나는 개수 중에서 최적의 개수를 찾아낼 수 있을 것인가였다.

초기 문제 풀이에서는 이분 탐색을 통한 upper와 lower를 찾아낸 후 그 사이에 있는 값들에 대한 총 line의 개수를 dict로 저장하는 방식을 채택했으나 정답을 구하지 못했다.

 

오히려 그보다 간단한 총체적인 이분 탐색을 통한 답을 구할 수 있었음을 확인할 수 있었다.

이에 대한 고민을 충분히 한 후 아래 솔루션을 본다면 충분히 이해가 갈 것이다. 

 

k, n = map(int, input().split())
l = sorted([int(input()) for _ in range(k)])
start, end = 1, l[-1]

while start <= end:
    mid = (start+end)//2
    lines = 0
    for i in l:
        lines += i//mid
    if lines >= n:
        start = mid+1
    else:
        end = mid-1
print(end)

위 코드에 대한 start, end, mid 순서의 값을 나타낸 것이다.

1 802 401
1 400 200
201 400 300
201 299 250
201 249 225
201 224 212
201 211 206
201 205 203
201 202 201
201 200 201

 

보이는 바와 같이 최종단에서 start와 end가 교차하는 부분이 생기고 이에 대한 조건을 토대로 while문이 종료된다.

종료된 후 end를 출력하면 끝

 

방법 2 - 메모리 30860KB / 시간 460ms / 코드 길이 285B

 

방법 1과 유사한 방법이며 조금 정리한 코드

 

k, n = map(int, input().split())
l = sorted([int(input()) for _ in range(k)])
start, end = 1, sum(l)//n
while start <= end:
    mid = (start+end)//2
    lines = sum([i//mid for i in l])
    if lines >= n:
        start = mid+1
        ans = mid
    else:
        end = mid-1
print(ans)