[BOJ_Python] 1654. 랜선 자르기

문제

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

 

사용 알고리즘

이분탐색

 

풀이

고려사항

1. N개 이상을 만들 수 있는 '최대' 길이인지

 

후기

1. 이분탐색의 기본 유형이다.

이분 탐색을 통해 랜선을 자를 길이를 계속 좁혀가며 탐색한다.

- 가능한 랜선의 길이는 1 ~ ($2^{31}$ - 1)으로 단순 모든 길이를 확인하면 약 $2^{31}$ 번 연산이 필요하다.

- 이진 탐색의 경우 $log_{2} {(max cable)}$으로 설정 후 K만큼 랜선 갯수 연산을 진행한다.

  따라서 시간 복잡도는 $O(K log_{2} {(max cable)}) $로 효율적이다.

 

코드흐름

1. 기준 길이를 통해 N개 이상의 랜선이 만들어 질 수 있는지 확인한다.

- N개 이상이 가능하다면, 기준 길이를 높인다.

- N개 이상이 가능하지 않다면, 기준 길이를 낮춘다.

2. 위의 탐색을 계속 진행하다가 start와 end가 최종 만나는 지점을 찾아 출력한다.

 

코드

import sys
input = sys.stdin.readline

N, K = map(int, input().split())

cable = [int(input()) for _ in range(N)]

start, end = 1, max(cable)

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

    cnt = 0
    for i in cable:
        cnt += i // mid

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

    else:
        end = mid - 1


print(result)

 

결과