[백준-Python] 랜선 자르기 : 1654번

🥈 Silver2

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

 

 

 

✅ 정답풀이

import sys
input=sys.stdin.readline

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

answer=1
left=1
right=2**31-1

#binary Search
while left<=right:
    mid=(left+right)//2
    count=0 # 생성되는 막대 개수
    for line in lines:
        count+=line//mid # mid로 인해 생성되는 막대 개수 카운트
        
    if count>=k: #오른쪽 보기
        answer=mid
        left=mid+1
    
    else:
        right=mid-1
print(answer)

메모리	실행시간
31120KB	88ms

 

이분탐색의 국룰 mid 찾고, target값의 크기 비교로 인해 left, right값 업데이트 해주기

하지만 처음에 count(막대 개수)==k(target)를 조건으로 answer를 출력하는 방식으로 풀었더니 오답이 나오길래 이유를 찾아보니...

 

K개의 랜선을 만들 수 있는 최대길이를 찾는것이기 때문에, 이와 같은 조건으로 답을 찾으면 최적의 최대길이를 놓칠 수 있다고 한다. 

K개 이상을 만들 수 있는 경우에도 가능한 최대한 길이를 찾아야하기 때문이다.

 

❗️  N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 

 

 

👉🏻 유사문제 : 나무자르기

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