[Baekjoon Online Judge] 백준 1654번 랜선 자르기(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 1654번 랜선 자르기

(Python)

(글쓴날 : 2020.04.06)

 

---

* Baekjoon Online Judge, 백준 1654번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 1654번 랜선 자르기

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

---

2) 풀이 과정

길이가 각기 다른 랜선들이 주어지고 얻고자 하는 랜선의 개수가 주어질 때, 랜선의 개수를 만족하는 최대 랜선의 길이를 출력하는 문제입니다.

 

저의 경우, 이분 탐색의 파라메트릭 서치를 적용해 문제를 해결하였습니다.

한 가지 주의해야 할 점이 있었는데, 최소 길이를 1부터 시작해야 0으로 나누는 연산을 피할 수 있습니다.

(1, 1 1과 같은 케이스의 경우 mid가 0이 돼버리므로 ZeroDivisionError가 발생합니다.

---

3) 코드

 

* Python 코드

import sys
input = sys.stdin.readline
 
K, N = map(int, input().split())
lans = [int(input()) for _ in range(K)]
 
left = 1
right = max(lans)
 
while left <= right:
    processdLans = 0
    mid = (right + left) // 2
 
    for lan in lans:
        processdLans += lan // mid
 
    if N <= processdLans:
        result = mid
        left = mid + 1
    else:
        right = mid - 1
        
print(result)

---