반응형
1654번: 랜선 자르기
첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그
www.acmicpc.net
코드
import sys
k,n = map(int,input().split())
arr = []
for _ in range(k):
arr.append(int(sys.stdin.readline()))
start = 1
end = max(arr)
while start <= end:
mid = (start+end)//2
cnt = 0
for i in range(k):
cnt += arr[i]//mid
if cnt >= n:
start = mid+1
else:
end = mid-1
print(end)설명
이진탐색을 사용하여 풀었다.
길이는 1부터 가장 긴 랜선의 길이 사이에 있어야 한다
mid 값을 구해서 만약 만들 수 있는 랜선의 개수가 n보다 크거나 같으면 이 값보다 작아질 필요가 없으므로 start 값을 mid+1로 바꿔준다.
n보다 작으면 더 작은 단위로 잘라줘야 하므로 end 값을 mid-1로 바꿔준다.
위 과정을 start가 end보다 커질 때까지 반복한다.
반응형
댓글