[알고리즘] 백준 1654 : 랜선 자르기 - S2

2023.05.11 풀이

import sys
input=sys.stdin.readline

arr=[]
k,n=map(int, input().split())
for _ in range(k):
    arr.append(int(input()))

arr.sort()
res=0
start=1
end=max(arr)

while start<=end:
    sum=0
    mid=(start+end)//2
    for i in arr:
        if i>=mid:
            sum+=i//mid
    if sum>=n:
        res=mid
        start=mid+1
    else:
        end=mid-1
print(res)

다른 풀이

import sys
input=sys.stdin.readline
def bifind(st,ed,K,N):
    global ans
    mid=(st+ed)//2
    cnt=0
    if st>ed:
        print(ed)
        return 
    for i in range(K):
        cnt+=lst[i]//mid
    if cnt>=N:
        bifind(mid+1,ed,K,N)
    if cnt<N:
        bifind(st,mid-1,K,N)
K,N=map(int,input().split())
lst=[int(input()) for _ in range(K)]
sum(lst)
bifind(1,sum(lst),K,N)

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과 같아지기만 하면 되므로, 커져도 end 값은 달라지지 않음.

check point

• 이진탐색은 무조건 정렬이 규칙. 근데 이 문제는 정렬이 필요하진 않음
• 런타임에러 -> ref