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