[Python/파이썬] 백준 1654번: 랜선 자르기 [이진 탐색]

내 코드

def find(lans, n,h,m):
    high = h
    min = m
    mid = (high + min)//2

    while min <= high:
        sum = 0
        for lan in lans:
            sum += lan//mid

        if sum >= n:
            min = mid + 1
        elif sum < n:
            high = mid - 1
    

        mid = (high + min)//2
    
    return mid


from sys import stdin
k, n = map(int,stdin.readline().split())
lans = []


for i in range(k):
    lans.append(int(input()))

high = max(lans)
min = 1

mid1 = find(lans,n,high,min)

print(mid1)

 

 

 

처음 작성한 코드

k,n = map(int,input().split())
lans = []

for i in range(k):
    lans.append(int(input()))

max = 1
sum = [0]

while True:
    sum.append(0)
    for lan in lans:
        sum[max] += (lan//max)
    if sum[max] == 0:
        break
    max += 1

a = 0


for i in range(max):
    if (a < i) & (sum[i] >= n):
        a = i

print(a)

전수 조사로 풀어보려 했지만... 시간 초과가 발생했다.

시간 초과가 되는 이유를 엄청 헤매고, 코드 수정도 많이 해봤지만 해결이 되지 않아 결국 구글링 했다.

방법은 이진 탐색을 사용하는 것이었다.

 

 

이진 탐색 코드

k,n = map(int,input().split())

lans = []

for i in range(k):
    lans.append(int(input()))

mid = max(lans)//2
high = max(lans)
min = 0

while True:
    sum = 0
    for lan in lans:
        sum += lan//mid

    if n == sum:
        break
    elif sum > n:
        min = mid + 1
        mid = (high + min)//2
    else:
        high = mid - 1
        mid = (high + min)//2
    
    if min > high:
        n += 1
        mid = max(lans)//2
        high = max(lans)
        min = 0
        
print(mid - 1)

 

분명 이진 탐색을 통해 시간초과는 해결했으나.. 이진탐색을 통해 나오는 결괏값이 최댓값이 아니었다.

최댓값을 찾기 위해, 다음과 같은 코드를 추가했으나..

 

k,n = map(int,input().split())

lans = []
lansum = 0

for i in range(k):
    lans.append(int(input()))

mid = max(lans)//2
high = max(lans)
min = 0

while True:
    sum = 0
    for lan in lans:
        sum += lan//mid

    if n == sum:
        break
    elif sum > n:
        min = mid + 1
        mid = (high + min)//2
    else:
        high = mid - 1
        mid = (high + min)//2
    
    if min > high:
        n += 1
        mid = max(lans)//2
        high = max(lans)
        min = 0


while True:
    sum = 0
    for lan in lans:
        sum += lan//mid

    if n == sum:
        mid += 1
    else:
        break
        
    
print(mid - 1)

 

또다시 시간 초과 발생... 다시 최대값을 구하는 코드를 짜면서 엄청난 삽질을 한 결과

다음과 같은 더러운 코드가 탄생했다..

 

def find(lans, n,h,m,l):
    low = l
    high = h
    min = m
    mid = (high + min)//2

    while True:
        sum = 0
        for lan in lans:
            sum += lan//mid

        if sum == n:
            break
        elif sum > n:
            min = mid + 1
        elif sum < n:
            high = mid - 1
    
        if min > high:
            if low == False:
                n += 1
            else:
                n -= 1
            high = h
            min = m
        mid = (high + min)//2
    
    return mid,n


k,n = map(int,input().split())


lans = []

for i in range(k):
    lans.append(int(input()))

if k == n:
    print(lans[0])
    exit(0)

high = max(lans)
min = 0


mid1,n1 = find(lans,n,high,min,False)
mid2,n2 = find(lans,n-1,high,min,True)
    
while True:
    mid3,n3 = find(lans,n,mid2,mid1,False)
    if mid1 == mid3:
        break
    if n3 == n1:
        mid1 = mid3

print(mid1)

 

물론 이 코드로도 시간초과 문제는 해결이 되지 않았고.. 결국 구글링을 통해 문제를 풀었다.

 

 

이 문제를 풀며 얻은 교훈은..

3시간 이상 투자해도 문제가 안 풀리면 하루 간격을 두고 풀어보고,

코드가 너무 복잡해진다고 느끼면 다시 생각해야겠다.