[백준] 1654번-랜선자르기 (Python)

 

 

이진탐색이 시간초과 해결의 Point였다.

 

처음에 이 문제를 우당탕탕 풀었을 때는 Case의 답 중 가장 큰 값에서 -1씩 해서 모두 돌려보는 과정으로 이 문제를 해결해보았다. 그러나 시간초과가 나왔다. 다른사람들 코드를 구경하다보니, start,end,mid가 있길래 '어 이거 이진탐색문항이구나..' 깨닫게 되었다.

 

알고보니 이진탐색을 활용하면 빠르게 풀이되는 문항이었다.

이진탐색은 https://stopmin.tistory.com/28 에 간단하게 정리해두었다!

 

내가 처음 짠 코드들은 둘 다 순차탐색을 활용한 코드였기에 시간초과가 나올 수 밖에 없었다.

 

 

내가 처음 짠 2개의 시간초과 코드들)

import sys
K, N = map(int,sys.stdin.readline().split())
string = list()
for _ in range(K):
    string.append(int(sys.stdin.readline().rstrip()))

ans_list = [0]*K

ans = sum(string)//N
while True:
    if sum(ans_list) == N:
        break

    ans -= 1
    for i in range(K):
        ans_list[i] = string[i]//ans
print(ans)

 

import sys
K, N = map(int,sys.stdin.readline().split())
string = list()
for _ in range(K):
    string.append(int(sys.stdin.readline().rstrip()))


ans = sum(string)//N

while True:
    tmp = 0
    for i in range(K):
        tmp += string[i]//ans
    if tmp == N:
        break
    else:
        ans -= 1

print(ans)

 

이진 탐색을 활용한 코드)

import sys
K, N = map(int,sys.stdin.readline().split())

string = [int(sys.stdin.readline()) for _ in range(K)]
start , end = 1, max(string)

while start <= end:
    mid = (start + end) // 2
    cnt = 0
    for w in string:
        cnt += w//mid

    if cnt >= N:
        start = mid + 1
    else:
        end = mid -1

print(end)