[백준] 1654 : 랜선자르기

백준 1654 문제 링크

문제가 이진탐색 문제임을 파악하지 못했음

• 내공의 부족으로 보임
• 더 많은 문제를 풀어보자!!

start = sum(len_list) // N

answer = 0
while True:
    if answer >= N:
        break
    else:
        start -= 1
        answer = sum([num // start for num in len_list])

# 시간초과 발생

이진탐색 공부

• 데이터의 범위가 10,000,000을 넘어가는 경우 (1천만 이상)
• 가장 큰 수를 기준으로 이진탐색 실행
• start, end, mid 활용하여 이진탐색 실행
• 이때, list 정렬 필요 (오름차순)

# 이진탐색 코드
## data : 가지고 있는 source 데이터
## target : 찾아야 하는 데이터
## start : 찾고자 하는 범위에서 가장 작은 쪽의 limit
## end : 찾고자 하는 범위에서 가장 큰 쪽의 limit


def binary_search(target, data):
	data.sort() # 오름차순 정렬
    start = 0
    end = len(data)
    
    while start <= data:
    	mid = (start + end) // 2
        if data[mid] == target:
        	return mid
       	elif data[mid] < target: 
        # target이 mid 보다 클 경우 -> start limit값을 mid 보다 큰 쪽으로 옮겨줘야 함
        	start = mid + 1
        else: 
        # target이 mid 보다 작을 경우 -> end limit값을 mid 보다 작은 쪽으로 옮겨줘야 함
        	end = mid - 1

랜선자르기 문제를 이진탐색 방식으로 다시 풀어보면,

K, N = map(int, input().split())
len_list = []
for _ in range(K):
    len_list.append(int(input()))

len_list.sort() # 이진탐색을 위해 list 정렬
start = 1
end = len_list[-1]

answer = 0

while start <= end:
    cnt = 0
    mid = (start + end) // 2

    for length in len_list:
        cnt += (length // mid)

    if cnt >= N: # 랜선의 개수가 N보다 크거나 같을 때 (랜선 길이를 길게 만들어야 할 필요가 있음)
        start = mid + 1
        answer = mid
    else: # 랜선의 개수가 N보다 작을 때 (랜선 길이를 짧게 만들어야 할 필요가 있음)
        end = mid - 1

print(answer)

++ 재귀함수를 활용하여 이진탐색을 구현해낼 수도 있다.

• 재귀함수 사용시 : RecursionError: maximum recursion depth exceeded in comparison 주의해야 함
  • import sys
  • sys.setrecursionlimit(10**7)
    설정을 통해 재귀의 한도를 높여줘야 함

# 재귀함수로 구현한 이진탐색
data.sort()

def binary_search_recursive(target, start, end, data):
	if start > end:
    	return None
    
    mid = (start + end) // 2
    if data[mid] == target:
    	return mid
    elif data[mid] < target:
    	start = mid + 1
    else:
    	end = mid - 1
        
    return binary_search_recursive(target, start, end, data)