🥈 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
'백준' 카테고리의 다른 글
[백준-Python] 좌표 압축 : 18870번 (0) | 2024.06.07 |
---|---|
[백준-Python] 콘서트 : 16466번 (0) | 2024.06.07 |
[백준-Python] 단어 정렬 : 1181번 (0) | 2024.06.07 |
[백준-Python] 회전하는 큐 : 1021번 (0) | 2024.06.05 |
[백준-Python] 프린터 큐 : 1966번 (0) | 2024.06.05 |