[백준] 1654 랜선 자르기
📌문제 링크
💡 문제 풀이
2805 나무 자르기 문제와 동일하게 랜선의 길이를 범위로 해서 이진탐색으로 풀이했다.
1. 0부터 랜선의 최대 길이까지를 이진 탐색의 범위로 설정한다.
(start = 0, end = max(line))
2. mid = (start + end) // 2 의 길이로 랜선을 잘랐을 때 랜선의 개수를 계산한다.
(각 랜선의 길이에서 mid만큼 나눈 값을 모두 더함)
3. 랜선의 개수가 부족한 경우 자를 랜선의 길이를 줄인다.
(if total < m: end = mid - 1)
4. 랜선의 개수가 충분한 경우 절단기의 높이를 높인다.
이 때, 랜선의 개수가 n보다 커도 n개를 만들긴 했기 때문에 결과값인 result에 mid 값을 저장한다.
(if total >= m : start = mid + 1, result = mid)
📋코드
k, n = map(int, input().split())
line = list()
for i in range(k):
line.append(int(input())) # append 시간복잡도 O(1)
# 이진 탐색을 위한 시작점과 끝점 설정
start = 0
end = max(line)
result = 0
while start <= end:
total = 0
mid = (start + end) // 2
if mid < 1:
mid = 1
for x in line:
# 잘랐을 때의 랜선의 개수 계산
if x >= mid:
total += x // mid
# 랜선의 개수가 부족한 경우 자를 랜선의 길이를 줄임
if total < n:
end = mid - 1
# 랜선의 개수가 n보다 클 경우 자를 랜선의 길이를 높임
else:
result = mid # 더 많이 만들었어도 n개 만든거니까 일단 기록
start = mid + 1
print(result)
Author And Source
이 문제에 관하여([백준] 1654 랜선 자르기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@saessak/백준-1654-랜선-자르기-Python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)