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

백준 온라인저지 1654 랜선 자르기

문제풀러 바로가기👇👇👇👇👇👇

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

 

 

 

문제풀이

---

이 문제는 이분탐색을 이용해야하는 문제이다.

start는 1로 잡고, 랜선 중 최대길이를 end로 정한 다음 이분 탐색을 하면 다음과 같다.

첫 번째 mid는 402cm이다. 402cm로 자르면 랜선이 5개 밖에 나오지 않기 때문에

mid를 mid = (start + mid - 1) // 2 로 조정해준다.

 

기준을 201cm로 랜선을 자르면 10개가 나오기 때문에 mid를 다시 조정해준다.

 

101cm로 자르면 랜선이 11개가 넘게 나온다. 일단 n값을 만족했기때문에 값을 저장해두고

start을 늘려서 최대값을 찾아준다.

위 과정을 반복하면 결국 아래의 결과가 나온다.

200cm일 때 랜선 11개도 만족하고 최대값인 조건도 만족한다.

이 논리를 코드로 구현하면 아래와 같다.

 

 

코드

import sys
input = sys.stdin.readline

k, n = map(int, input().split())
lan = []
for _ in range(k):
    lan.append(int(input()))

start = 1
end = max(lan)
result = 0

while start <= end:
    cnt = 0
    mid = (start + end) // 2

    for i in lan:
        cnt += (i // mid)

    if cnt >= n:
        result = mid
        start = mid + 1

    else:
        end = mid - 1

print(result)

 

*** 주의사항 ***

일반 이분탐색처럼 start를 0으로 설정하고 프로그램을 돌리면 런타임에러(ZeroDivisionError)가 발생한다.

 

 

*** 참고 - 런타임에러가 발생하는 경우 ***

1. 배열에 할당된 크기를 넘어서 접근했을 때
2. 전역 배열의 크기가 메모리 제한을 초과할 때
3. 지역 배열의 크기가 스택 크기 제한을 넘어갈 때
4. 0으로 나눌 떄
5. 라이브러리에서 예외를 발생시켰을 때
6. 재귀 호출이 너무 깊어질 때
7. 이미 해제된 메모리를 또 참조할 때

**********************************************