백준 - [Silver 3] 1654번 랜선 자르기

문제링크: https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

이분탐색의 기본문제입니다. 이분탐색 같은 경우는 조건을 세우는 것이 중요합니다.

1. 이분탐색으로 구하고자 하는 수

2. 이분 탐색의 기준(left right를 움직이는 기준)

---

문제 설명

- K: 기존에 가지고 있는 랜선의 개수

- N: 필요한 랜선의 개수 

- K개의 선이 주어지는데 N개를 만족하며 최대로 구할 수 있는 선의 길이를 구하는 문제입니다.

- 이분탐색으로 구하고자 하는 수: 최대 선의 길이

- 이분탐색의 기준: 선의 길이로 만들 수 있는 선 개수

말로 풀어쓰니까 더 어려운 것 같습니다. 코드 보시면 이해가 더 수월하실 겁니다.

---

풀이방법

from sys import stdin

# stdin = open("input.txt", "r")
# K: 기존에 가지고 있는 랜선의 개수
# N: 필요한 랜선의 개수 
K, N = map(int, stdin.readline().split())

# K개의 선 입력
lines = [int(stdin.readline()) for _ in range(K)]

# 이분탐색
# 구하고자 하는 것: 최대 랜선의 길이(정답)
# 이분 탐색의 기준: 랜선의 개수
start = 1
end = max(lines)

# start가 end보다 커지는 경우
while start <= end:

    # mid: 현재 랜선의 길이
    mid = (start + end) // 2

    # 각 랜선에서 만들 수 있는 선의 개수 구하기
    line_count = sum([line // mid for line in lines])

    # 선의 개수가 N보다 크면
    # 최소 선의 길이를 늘려야 함
    if line_count >= N:
        start = mid + 1

    # 위에 말과 반대
    elif line_count < N:
        end = mid - 1
    
print(end)