BOJ 1654 파이썬

행행·2022년 6월 16일
0

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

풀이

  • 이진탐색활용
  • 가장 큰 길이와 작은 길이(=1)의 중간값으로 먼저 잘라보고 cnt에 더한다.
  • cnt의 값이 최종적으로 잘라야할 정도(=N)보다 작은경우 잘라야할 크기를 키워준다
    • start = mid+1
  • cnt의 값이 최종적으로 잘라야할 정도(=N)보다 큰 경우 잘라야할 크기를 줄여준다.
    • end=mid-1
  • 그렇게해서 나온 end값 출력
#k = 가지고 있는 갯수, n = 잘라야할 랜선 갯수
k,n = map(int, input().split())
a=[]
for _ in range(k):
    a.append(int(input()))

start =1
end = max(a)

while start<=end:
    mid = (start+end)//2
    cnt=0
    for i in a:
    	
        #잘라서 몫만
        cnt+=i//mid
    if cnt>= n:
        start =mid+1
    else:
        end=mid-1

print(end)

profile
성장하려고 분투 중인 개발자

0개의 댓글