1654. [Python]랜선 자르기

1. 문제

 

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

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 128MB
• 이분 탐색

 

3. 파이썬 코드

 

# 인풋 처리
import sys
# 많은 인풋
input = sys.stdin.readline

N, K = map(int,input().split())
# 랜선 길이
num_list = []
# 최대값 최소값 설정
right = 2**31 - 1
left = 1

for _ in range(N):
    num_list.append(int(input()))
# 이분 탐색
while left <= right:
    # 중앙값 설정
    middle = (left+right) // 2
    # 개수 체크
    cnt = 0
    # 중앙 값으로 랜선을 자른 개수 체크
    for num in num_list:
        cnt += (num // middle)
    # 만약 개수가 목표인 K 보다 작으면 right 는 middle -1 외의 경우 left 는 middle + 1
    if cnt < K:
        right = middle - 1
    elif cnt >= K:
        left = middle + 1

print(right)

 

4. 문제를 풀고난 후 생각

 

• 이분 탐색문제로 right 값으로는 랜선 최대 길이 left 로는 최소 길이인 1로 설정한 후 이분탐색을 진행하며 middle 값으로 랜선을 자른 경우 개수를 체크해준다.
• middle 값으로 자른 값의 개수로 내가 목표하는 K 값에 도달하게 되면 left는 최소값 right는 최대 값이 되므로 최대 길이를 구하기 때문에 right 값을 출력해주면 문제에서 요구하는 부분을 구할 수 있다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 이분 탐색