백준 실버2 이분탐색 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이]

⌛ 시간 초과 (후 구현)

def binary_search(lines,N):
    start = 1
    end = lines[0]
    ans_list = []

    if N <= sum([line//end for line in lines]):

        print(end)
        return

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

        for line in lines:
            cnt += line//mid

        if cnt >= N:
            start = mid+1
            ans_list.append(mid)
        
        if cnt < N:
            end = mid-1

    return print(max(ans_list))

K,N = map(int,input().split())

ans = -1

lines = []
for _ in range(K):
    lines.append(int(input()))
    
lines.sort(reverse=True)

binary_search(lines,N)

이분 탐색 문제입니다. 문제에서의 요구사항은 target의 위치값을 찾는 기본적인 이분 탐색과 다르게 조건에 맞는 target의 최대값을 구하는 것이였습니다.

Binary Search를 활용해야 한다는 포인트는 이해하였지만 탐색하는 범위 (start, end) 초기값을 잘못 입력하여 시간 내에 완전히 풀어내지는 못하였고 이후 해결하였습니다.🧸🧸🧸

[다른 사람의 풀이1]

import sys
K, N = map(int, input().split())
lan = [int(sys.stdin.readline()) for _ in range(K)]
start, end = 1, max(lan) #이분탐색 처음과 끝위치

while start <= end: #적절한 랜선의 길이를 찾는 알고리즘
    mid = (start + end) // 2 #중간 위치
    lines = 0 #랜선 수
    for i in lan:
        lines += i // mid #분할 된 랜선 수
        
    if lines >= N: #랜선의 개수가 분기점
        start = mid + 1
    else:
        end = mid - 1
print(end)

'나의 풀이'와 유사하게 분할된 랜선의 수가 목표 랜선 수(N)보다 같거나 클 때, start 값을 증가시키며 최종적으로 end값을 출력하는 방식이였습니다.

[다른 사람의 풀이2]

import sys
input = sys.stdin.readline

K, N = map(int, input().split())
lan = [int(input()) for _ in range(K)]
end = max(lan)

def lan_length(n):
    count = 0
    for item in lan:
        count += item // n
    return count

def binarySearch(start, end, N):
    if start > end:
        return end
    
    mid = (start + end) // 2
    length = lan_length(mid)
    if length >= N:
        return binarySearch(mid+1, end, N)
    else:
        return binarySearch(start, mid-1, N)

print(binarySearch(1, end, N))

이진 탐색을 재귀함수로 구현한 풀이입니다. 재귀함수로 구현하기 위해 파라미터(start,mid,end)값들을 갱신하여 돌아가는 방식입니다.🐥🐥🐥

감사합니다.