1654번 랜선자르기 파이썬

문제

입력과 출력

내가 시도한 풀이

없다. 이다음 줄부터는 내가 징징대는거니까 다음 쪽으로 넘어가도 좋다.

머리가 그냥 멍해졌다.

진짜 어떻게풀지?

이분탐색은 그냥 배열에서 원소를 선형탐색보다 빨리 찾을 수 있는거 아니었나?..

일단 저게 이분탐색으로 풀수가있는건가?..

30분정도 고민하다가 구글의 도움을받았다.

구글의 도움을 받아서 틀은 잡혔지만

그래도 멍했다... 진짜 미칠거같았당...

 

 

풀이

start 1

end를 입력받은 케이블 중 가장 긴 케이블의 길이

이렇게 잡아놓고 길이로 이분탐색을 합니다.

4 11
802
743
457
539

가장 긴 랜선은 802

803 //2

401

길이 802의 랜선은2개 자를수있고

743은 1개

457도 1개

539도 1개

총 5개

근데 성원이가 가져가려는 개수는 11개인데

우리가 더 적게 잘랐죠

그럼 길이를 높여야할까요 내려야할까요?

내려야합니다.

end = mid -1

약간 감이 오시죠 이제

 

코드

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

Cable = [int(input()) for _ in range(K)]

start = 1

end = max(Cable)


while start <= end:
    count = 0
    mid = (start+end)//2
    for i in Cable: 
        count += i//mid #mid값으로 자른 갯수
    if count >= N:  #N이 11이고 mid값으로 자른 갯수가 14거나 그러면 길이를 늘려줍니다
        start = mid + 1 #근데 같아도 올림 이건 아래 글에서 설명할게요
    else:
        end = mid - 1

print(end)

? 왜 count == N

break

print(mid)를 하지 않는거지?

if count >= N: 같은경우에도 위 높이를 올리지?

 

할수도있는데 성원이가 가져갈수있는길이랑 

딱 떨어지지 않을수도있고

최대값을 구해야하기때문에

mid가 198인경우

802 //198 4개

743//198 3개

457 // 198 2개

539 //198 2개

4+3+2+2

얘도 11개네요

근데 최대값을 구하라고했으니까

이렇게  갯수가 딱 떨어져도 

길이를 늘려줍니다.

결국 최대값에 도달했을때는

end = mid - 1밖에못하고

while 문을 탈출하게되면서

end값이 최대 길이가 되는겁니다.

 

파이썬으로 제출하는데 자꾸 시간초과나면서

아니 맞는데왜틀리지가 계속 나오면 진짜 맞는데 파이썬이라 시간초과가 나오는 걸수도있습니다.

ㅠㅠ