https://www.acmicpc.net/problem/1654
1654번: 랜선 자르기
첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그
www.acmicpc.net
난이도: 실버2
소요시간: 60분, 엣지케이스 관련 힌트 참고함
최대로 나올수 있는 값을 end로 정했다.
1~end를 이분탐색하여서 정답을 찾았다.
import sys
K,N = map(int,sys.stdin.readline().split())
end=0
cableList=[]
for _ in range(K):
temp=int(sys.stdin.readline())
cableList.append(temp)
end+=temp
end = end//N
start=1
midList=[]
while start<=end:
mid = (start+end)//2
count=0
for cable in cableList:
count+=cable//mid
if count >=N:
start=mid+1
else:
end=mid-1
midList.append([mid,count])
result=[]
for i in range(-(len(midList)),0):
if midList[i][1] >=N:
result.append(midList[i][0])
print(max(result))
'Problem Solving > 이진 탐색' 카테고리의 다른 글
BOJ14425 문자열 집합 (0) | 2024.02.13 |
---|---|
이분 탐색 개념 (0) | 2024.02.13 |
BOJ2343 기타 레슨 (0) | 2023.04.04 |
떡볶이 떡 만들기 (0) | 2023.01.09 |
부품 찾기 (0) | 2023.01.09 |