백준 1654 문제 분석 python

🐒 랜선 자르기

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

✍ 풀이

import sys


k, n = map(int, input().split())

lan = [int(sys.stdin.readline()) for _ in range(k)]
start = 1
end = max(lan)

#이분탐색
while start <= end:
    mid = (start + end) // 2
    count = 0
    for i in lan:
        count += i // mid
    if count >= n:
        start = mid + 1
    else:
        end = mid - 1

print(end)

참고한 블로그

이분탐색 유형이란걸 알고서 문제를 봤는데 어떻게 풀어야할지 접근도 못하겠어서 구글링을 했다.

---

🧠 문제 이해

주어진 k개의 랜선들을 몇 cm씩 잘라야 가장 긴 n조각난 랜선을 얻을 수 있는가?

import sys


k, n = map(int, input().split())

lan = [int(sys.stdin.readline()) for _ in range(k)]


for i in range(1,2**31):
    count =0
    for j in lan:
        count += j // i 
    if count < n:
        break
print(i-1)

랜선은 가장 길게 자르면 2^31 -1 cm 씩 자를 수 있다.

k개의 랜선을 1cm씩 자르고 확인하고, k개의 랜선을 2cm씩 자르고.. k개의 랜선을 2^31 -1 cm 씩 자르면 시간 초과가 발생한다.

그래서 이분탐색 알고리즘을 사용해야한다.

---

import sys


k, n = map(int, input().split())

lan = [int(sys.stdin.readline()) for _ in range(k)]
start = 1		# 이분탐색 시작점 1로 초기화
end = max(lan)		#이분탐색 끝점 초기화

#이분탐색
while start <= end:		# 끝점이 시작점보다 작아지면 종료
    mid = (start + end) // 2
    count = 0	# 조각난 갯수 저장
    for i in lan:	# 주어진 랜선들 순회
        count += i // mid	# 총 몇조각 났는지 세기 
    if count >= n:		# 조각이 많이 나오거나 알맞게 나오면
        start = mid + 1		# 시작점을 오른쪽으로 옮기기
    else:		#조각이 적게 나왔으면
        end = mid - 1 	# 끝점을 왼쪽으로 옮기기

print(end)

처음 이분탐색 구간은 1부터 max(lan)인데, 주어진 가장 긴 랜선이 802이면 803 부터는 한조각도 자를 수 없게 되기 때문이다.