백준 1654번: 랜선 자르기 (Python)

접근

이분탐색 알고리즘을 이용한 문제였다.

2021.04.05 - [코딩/백준 (Python)] - 백준 1920번: 수 찾기 (Python)

백준 1920번: 수 찾기 (Python)

가장 먼저 끈 길이 탐색의 범위를 정해주기 위해 끈 길이의 범위를 생각해보았다.

예를 들어 주어진 끈 중 가장 긴 끈을 목표 개수로 나눈 값이 끈이 될 수 있는 길이 중 최소값이며, 모든 끈을 더한 값을 목표 개수로 나눈 값(모든 끈을 남김 없이 효율적으로 썼을 때)이 끈이 될 수 있는 길이 중 최대값이다.

예를 들어 주어진 끈 K가 [1, 2, 3, 3] 일 때 필요한 랜선의 개수 N이 3으로 주어진다면, 끈은 최소 1 (3 // 3 = 1) 에서 부터, 3 ((1+2+3+3) // 3 = 3)의 범위를 가지게 된다. 보통 K에서 주어진 끈이 한개일 때 최소값을 정답으로 가지며, 모든 끈을 남김 없이 다 사용할 때 최대값을 정답으로 가지게 된다.

이렇게 구해진 끈 길이의 범위에서 이분탐색을 이용하여 필요한 랜선의 개수 N을 만족하는 최대 길이의 끈을 탐색하게 된다.

코드

import sys

sys.setrecursionlimit(10**6)
n, need = map(int, sys.stdin.readline().split())
lines = []
for _ in range(n):
    lines.append(int(sys.stdin.readline()))
lines.sort()

minl = lines[-1] // need
maxl = sum(lines) // need + 1


def divide(lines, l):
    cnt = 0
    for i in range(len(lines)):
        cnt += lines[i] // l
    return cnt


def binarysearch(minl, maxl, target):
    midl = (minl + maxl) // 2
    if minl >= maxl - 1:
        return minl  # divide(lines, length) == target 을 만족하는 최대 length를 return하게 된다.
    if divide(lines, midl) < target:
        return binarysearch(minl, midl, target)
    else:
        return binarysearch(midl, maxl, target)


print(binarysearch(minl, maxl, need))

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!