[백준/파이썬] 1654번 랜선 자르기 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1654번 랜선 자르기
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

K개의 랜선을 잘라 길이가 같은 랜선 N개 이상을 만들 때, 가능한 최대 길이를 구하는 문제입니다.

코드

import sys;read=sys.stdin.readline
k,n=map(int,read().split())
l=[int(read())for _ in range(k)]
a,b,r=1,max(l),0
while True:
    m=(a+b)//2
    s=0
    for i in l:s+=i//m
    if s<n:b=m-1
    else:
        r=max(r,m)
        a=m+1
    if a>b:break
print(r)

설명

길이 m으로 잘랐을 때 만들 수 있는 개수 s를 계산합니다.

• s < n: 길이를 줄여야 하므로 왼쪽 탐색
• s >= n: 가능한 길이이므로 답 후보 갱신 후 더 긴 길이 탐색

이분 탐색 종료 후 저장된 최대 가능 길이를 출력합니다.

---

• 백준 문제풀이 전체 목록 보기

---