문제

' 1654번 랜선 자르기 '
https://www.acmicpc.net/problem/1654

Check point

📌 이진 탐색/ 이분 탐색/ binary search

• 자료의 중앙에 있는 원소를 고른다.
• 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다.
• 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해서 새로 검색을 수행한다.
• 찾고자 하는 값을 찾을 때까지 위의 과정을 반복한다.

기본 코드

💡 반복문 사용

def binary(arr, key):
    start, end = 0, len(arr) - 1
    while start <= end:
        middle = (start + end) // 2
        if arr[middle] == key:  # 검색 성공
            return True
        elif arr[middle] > key:
            end = middle - 1
        else:
            start = middle + 1
    return False  # 검색 실패

💡 재귀 사용

def binary(arr, start, end, key):
    if start > end:  # 검색 실패
        return False
    else:
        middle = (start + end) // 2
        if arr[middle] == key:  # 검색 성공
            return True
        elif arr[middle] > key:
            binary(arr, start, middle - 1, key)
        elif arr[middle] < key:
            binary(arr, middle + 1, end, key)

📌 문제 조건

• N개보다 많이 만드는 것도 N개를 만드는 것에 포함되므로 total >= M 인 값은 모두 고려해야 한다.

코드

python

💡 반복문 사용

K, N = map(int, input().split())
lst = [int(input()) for _ in range(K)]
start, end = 1, max(lst)  # 1을 시작, 최댓값을 끝
while start <= end:  # 반복문 종료 조건
    mid = (start + end) // 2  # 중앙 원소 고르기
    total = 0  # 랜선 갯수
    for l in lst:
        total += l // mid  # 중앙값 만큼 랜선을 자르면 얻을 수 있는 최대 갯수 = 랜선길이 // 중앙값
    if total >= N:
        start = mid + 1
    else:
        end = mid - 1
print(end)

다른 방법 1

💡 반복문 함수 사용

def binary(lst, N):
    start, end = 1, max(lst)
    while start <= end:
        mid = (start + end) // 2
        total = 0  # 랜선 갯수
        for l in lst:
            total += l // mid
        if total >= N:
            start = mid + 1
        else:
            end = mid - 1
    return end

K, N = map(int, input().split())
lst = [int(input()) for _ in range(K)]
print(binary(lst, N))

다른 방법 2

💡 재귀 사용

def binary(lst, start, end, N):
    global result
    if start > end:  # 검색 실패
        return
    else:
        mid = (start + end) // 2
        total = 0
        for l in lst:
            total += l // mid
        if total >= N:
            result = mid
            return binary(lst, mid + 1, end, N)
        else:
            return binary(lst, start, mid - 1, N)


K, N = map(int, input().split())
lst = [int(input()) for _ in range(K)]
start, end = 1, max(lst)
result = 0
binary(lst, start, end, N)
print(result)