[BOJ][Python] 1654 랜선 자르기

Overview

• 체감 난이도: ★★☆☆☆
• 문제 레벨: 실버 2
• 문제 유형: 이분탐색
• 풀이 상태: 답안참고 / 스스로 해결
• 추후: 다시 풀어보기 / 간단 복습 / 완벽 이해 

---

[문제]

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

 

[코드]

(시간초과코드)

k, n = map(int, input().split())
arr = [int(input()) for _ in range(k)]

tmp = sum(arr)//n

while True:
    cnt = 0
    for i in range(len(arr)):
        cnt += arr[i] // tmp

    if cnt == n:
        print(tmp)
        break

    tmp -= 1

 

 

(코드)

막대들을 자를 수 있는 최소 길이: 1 , 최대 길이: 막대들 중 가장 긴 막대의 길이

mid: 현재 시도할 막대 길이로 설정한다. → (start + end) // 2

막대 개수 계산: mid 길이로 막대들을 자를 때 몇 개의 조각이 나오는지 계산한다. 

k, n = map(int, input().split())
arr = [int(input()) for _ in range(k)]

# 이분 탐색 범위 설정
start = 1
end = max(arr)

# 이분 탐색 수행
result = 0
while start <= end:
    mid = (start + end) // 2  # 현재 길이 설정
    cnt = sum(x // mid for x in arr)  # 막대를 현재 길이로 잘라 얻을 수 있는 개수

    if cnt >= n:
        # 길이를 늘려서 더 큰 길이를 시도
        result = mid
        start = mid + 1
    else:
        # 길이를 줄여서 시도
        end = mid - 1

print(result)