[백준] 1654번 랜선 자르기, 시간초과 - 이분탐색(풀이 암기)

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

1654번: 랜선 자르기

 

 

시간 초과 나온 풀이

# BOJ_1654
import sys
# 입력
k, n = map(int, input().split())
lines = []
for _ in range(k):
    lines.append(int(sys.stdin.readline()))


# 전체 합을 k로 나눈 값에서 내림차순으로 시작한다.
sum = 0
for line in lines:
    sum += line
# //은 몫(정수), /은 나눈 값(float)
max_length = sum // n
for length in range(max_length, 0, -1):
    line_num = 0
    for line in lines:
        line_num += (line // length)
    if line_num >= n:
        print(length)
        break

답은 맞게 나온다.

나는 랜선 길이를

정수 몫 = 가지고 있는 랜선들의 총 길이 합  / n(원하는 랜선 갯수)

으로 시작해서

내림차순으로 n이상 되는 값을 찾으려고 했다.

시간 복잡도는 O(랜선 총 길이 합에서 원하는 랜선 갯수(n)를 나눈 몫 x 가지고 있는 랜선의 갯수)

 

 

이 문제는 찾아보니 이분탐색으로 풀어야 시간초과가 나오지 않는다고 한다.

시간 복잡도는 O(log(가진 랜선 길이 중에서 최댓값) x 가지고 있는 랜선의 갯수)

https://claude-u.tistory.com/443

#390 백준 파이썬 [1654] 랜선 자르기 - 이분탐색

 

 

# BOJ_1654
import sys
# 입력
k, n = map(int, input().split())
lines = [int(sys.stdin.readline()) for _ in range(k)]
start, end = 1, max(lines) # 이분탐색 처음과 끝 위치

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

 

 

이분 탐색 구현 레퍼토리는 외워 두어야겠다.

중간값을 기준으로 start = mid + 1, end = mid - 1