[ 백준 ] 1654번 - 랜선 자르기 (Python)

기본 정보

• Level: silver 3
• Problem Link: 랜선 자르기
• Problem Number: 1654
• My Solution Link: 나의 풀이
• Algorithm I used : 이진탐색(binary search)

문제

• 길이가 제각각인 K개의 랜선을 가지고 같은 길이의 랜선 N개를 만들어야 한다.
  • 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)
• 가정사항
  • 랜선을 자르거나 만들 때 손실되는 길이는 없다.
  • 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다.
  • 자를 때는 항상 cm 단위로 정수 길이만큼 자른다.
  • N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다.
• N개를 만들 수 있는 랜선의 최대 길이?

• 예제

    <입력>
    4 11
    802
    743
    457
    539
    → 802cm, 743cm, 457cm, 539cm 4개의 랜선을 가지고 11개를 만들어야 하는 상황
      
    <출력>
    200
    → 최대 200cm씩 자르면 랜선 11개를 만들 수 있다.
  

알고리즘

• 기본적인 이진탐색과 달리 역으로 searchNum을 찾아야 하는 상황
• 각 수열에서 middle 단위가 몇 번 나오는가?
  • 전체 개수가 원하는 개수보다 작다면 단위 길이를 줄이기
  • 전체 개수가 원하는 개수보다 크면 단위 길이를 늘리기

나의 풀이

• 너무 구현하는 데 어려움을 겪어 구글링 한 뒤 풀어봤다.
  • 하지만 맨 마지막에 middle이 아니라 right을 출력하는 이유를 이해하지 못했다.

# 가지고 있는 랜선 수, 만들고 싶은 랜선 수
k,n = map(int, input().split())

# 각 랜선 길이 가지고 있는 리스트
lans = [int(input()) for _ in range(k)]

# 초기 설정 (index가 아니라 실제 수를 지정한다!)
left, right = 1, max(lans)

### 이진탐색 ###
while left <= right:
    middle = (left + right) // 2  # 역시 index가 아니고 실제 수
    cnt = 0  # 만들 수 있는 랜선 개수

    for lan in lans:
        cnt += lan // middle  # 분할된 랜선 개수

    if cnt < n:  # 랜선을 너무 큼지막하게 자른 경우
        right = middle - 1
    else:  # 랜선을 너무 잘게 자른 경우
        left = middle + 1

print(right)