[Python] 백준1654 랜선 자르기

25 Dec 2022 in Study on Algorithm

백준1654 랜선 자르기 링크

문제

예제 입력

---

코드

import sys

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

def Binary_Search() :
    res = 0
    st, end = 1, max(arr)

    while st <= end:
        mid = (st + end) // 2

        sum = 0
        for line in arr :
            sum += line // mid
        if sum >= n :
            if res < mid :
                res = mid
            st = mid + 1
        else :
            end = mid - 1
    return res

print(Binary_Search())

설명

파이썬을 통해서 사용자로부터 입력받아 자료형 리스트를 사용하여 랜선 자르기을 구현했습니다. 같은 크기로 잘랐을때 N개를 만족하는 최대 길이를 구하기 위해서 이진 탐색으로 접근합니다. (기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자.) 가정을 보고 정해진 값을 빠르게 접근해야 한다는 것을 깨달았습니다.

---

정리

import sys

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

num = 1
while True:
    sum = 0
    for i in arr :
        sum += i // num
    if sum < n :
        break
    num += 1

print(num - 1)

처음에는 브루트 포스 방식으로 해결했지만 시간 초과가 발생했습니다.

---

결과