백준(BAEKJOON) 1654 랜선 자르기 using Python

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

1654번: 랜선 자르기

문제 설명

 

주어진 랜선(K)개를 통해서 길이가 똑같은 랜선(N)개를 만들 때 최대 길이를 구하는 문제이다.

Input

input값을 통해서 어떤 알고리즘을 쓸건지 판단한다. 이 문제는 K는 10000 이하의 자연수고 N은 1000000이하의 자연수다.

그러므로 완전 탐색은 못하고 탐색중에 시간 복잡도를 줄이는 탐색이 필요하다.

그래서 저는 값을 찾기 가장 간단한 방법인 이분탐색을 선택해서 풀었습니다.

코드는 아래와 같고 주석을 통해서 코드를 짠 방식을 적었다.

# 결국 값을 탐색하는 거지만 시간 복잡도를 줄일 필요가 있다.
# 그래서 이분탐색을 선택했다.
from sys import stdin

K, N = map(int, stdin.readline().split())
lst = [int(stdin.readline()) for _ in range(K)]
# 큰 값을 먼저 보기 위해서 정렬해서 시작했다.
lst.sort(reverse=True)
# 시작값을 최소 자연수1 , 끝값은 최대값을 선택했다.
s, e = 1, lst[0]
# 이분탐색
while s <= e:
    mid = (s+e) // 2
    num = 0
    for l in lst:
        num += l//mid
        # 이미 충족을 한다면 시작 값을 mid + 1 해주고 break 하기
        if num >= N:
            s = mid + 1
            break
    # 충족을 못한다면 끝 값을 mid - 1을 해준다.
    else:
        e = mid - 1
# 최댓값을 찾으므로 e를 선택 만약 최솟값을 찾기 위해서는 s를 선택하면된다.
print(e)