[python] 백준 1654 - 랜선 자르기

출처 : 백준, https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

# 주어진 끈 들은 동일한 길이로 잘라 목표 개수만큼 만들어야한다.

# 길이와 목표 개수가 주어질 때, 목표 개수로 만들 수 있는 잘린 길이의 최대 길이를 구하시오.
# 가진 랜선의 개수      1 <= k <= 10,000
# 필요한 랜선의 개수    1 <= n <= 1,000,000
# 각 랜선의 길이        1 <= length <= (2^31 - 1)

 

 

먼저, 생각해야 할 부분

 

1. 잘린 후의 로프 길이의 최댓값은 모든 로프의 길이의 총합을 목표 개수로 나눈 몫이다.

     즉, 탐색 범위는 1 ~ (로프의 총합) // (목표 개수)

 

2. 자른 후의 랜선의 길이를 탐색해야하는데 랜선의 길이는 최대 2^31 - 1까지 될 수 있다..

     최악의 경우 1부터 2^31 - 1까지 탐색하는 선형 탐색은 O(N)의 시간 복잡도를 가지는 만큼 시간이 오래 걸릴 것이므로,

     O(logN)의 시간 복잡도만에 돌 수 있는 이분 탐색으로 접근하자.

 

---

 

풀이

 

import sys
def input():
    return sys.stdin.readline().rstrip()

def calcCutLopeCount(length_list, cut_length): # 실제 잘린 로프의 개수를 구하는 함수
    answer = 0

    for lope in length_list:
        answer += lope // cut_length

    return answer

def binarySearch(start, end, target, length_list): #이진 탐색
    mid = (start + end) // 2

    if start == mid: # start + 1 == end
        return mid

    cut_lope_count = calcCutLopeCount(length_list, mid)

    if cut_lope_count < target:
        # 자른 개수의 총 합이 목표 개수보다 작으므로, 길이를 줄여야한다. -> 작은 쪽 탐색
        return binarySearch(start, mid, target, length_list)
    elif cut_lope_count >= target:
        # 자른 개수의 총 합이 목표 개수보다 크므로, 길이를 늘려야한다 -> 큰 쪽 탐색
        # cut_lope_count가 target이 나와도 cut_length는 더 커질 수 있다. -> 같은 쪽 포함
        return binarySearch(mid, end, target, length_list)

def solution(k, target, length_list):
    max_length = sum(length_list) // target

    start = 1
    end = max_length + 1

    return binarySearch(start, end, target, length_list)

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

print(solution(k, target, length_list))

 

---

 

알게 된 점

 

이진 탐색(이분 탐색)에서 헷갈리는 것들

 

1. 조건을 충족한 값이 1개 뿐인지 생각해보자.

 

이 경우는 199로 잘라도 11개, 200으로 잘라도 11개를 만들 수 있다.

즉, 목표 개수로 자른다고 하더라도, 조건을 충족하는 값이 여러 개가 될 수 있다.

 

2. 여러 개일 경우 조건을 충족하는 값의 방향을 따져보자.

 

조건을 충족하는 값이 여러 개일 경우, 정답이 요구하는 방향을 따져보자.

최댓값이라면 조건을 충족하는 값이 나와도 더 큰 쪽에서 정답이 존재할 수도 있고,

최솟값이라면 조건을 충족하는 값이 나아도 더 작은 쪽에서 정답이 존재할 수 있다.

단, 해당 값이 최솟값/최댓값일 수도 있기 때문에 해당 값을 포함해서 탐색해야한다.

 

즉, 최댓값이라면, 현재 탐색한 것을 포함하면서 큰 쪽을 탐색해야하고

최솟값이라면, 현재 탐색한 것을 포함하면서 작은 쪽을 탐색해야한다.

 

3. 종료 조건을 찾아보자.

 

이분 탐색은 재귀 함수를 통해 구분하는 경우가 많다. 때문에 종료 조건이 중요하다.

예를 들어 위 함수에서 start = 200, end = 201을 탐색한다면 mid = 200이 나온다.

만약 이를 다시 조회한다면, [200, 201]을 무한히 탐색하며 무한 루프를 돌게 된다.

즉, start == mid가 종료 조건이 된다.

 

4. 양 끝 값 조회여부를 살펴보자.

 

위 함수에서 종료 조건은 start == mid이다.

만약 배열이 [1, 2, 3, 4]이고 정답이 4인 상황에서, [3, 4]를 조회한다면 start = 3, mid = 3으로 종료된다.

4를 조회하지 못하는 것이다.

즉, end 값을 조회하지 못하므로, 처음 시작 시 end 값을 1 늘려 끝 값을 조회할 수 있도록 포함시켜준다.

 

Github

GitHub - bh2980/Algorithm-Problem: 알고리즘 풀이 흔적들