[Python] 백준 1654 랜선 자르기 | 이진 탐색 | 시간 초과

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

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

1654번: 랜선 자르기

 

 

문제 해결 포인트

- N의 범위가 크므로 이진탐색으로 풀이해야 한다.

- 길이가 가장 긴 랜선을 end값, 0을 start값으로 두고 중간 값으로 mid를 선언한다.

 

- start와 end가 교차되는 지점에서 종료하는 while문을 작성하여 최대 길이를 찾는다.

- mid를 기준으로 모든 랜선 별 생성되는 랜선 개수를 모두 더한다

- 총 합(cnt)이 N보다 크거나 같다면 = 만들 수 있는 랜선 개수가 원하는 개수보다 크다면

   mid 길이를 늘려 개수를 낮춰야 한다. 그러므로 start = mid+1

- 그 반대는 end = mid - 1

 

 

작성 코드

import sys
input = sys.stdin.readline

K, N = map(int, input().split())
numbers = []
maxNum = 0

for i in range(K):
    number = int(input())
    numbers.append(number)

start = 0
end = max(numbers)
while start <= end:
    cnt = 0
    mid = (start + end)//2
    if mid == 0:  # start와 end가 모두 0일 때
        break
    for n in numbers:
        cnt += n//mid

    if cnt >= N:  # 주의 : cnt == N 찾더라도 최대 값을 찾아야 함
        start = mid + 1
    else:
        end = mid - 1

print(end)

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚

 

REFERENCE

https://claude-u.tistory.com/443