[BOJ] 1654번 랜선 자르기 / 사용언어 : 파이썬(python)

※ 문제링크 

1654번: 랜선 자르기

 ※ 관련개념 및 참고사이트 

[알고리즘] 이분 탐색 / 이진 탐색 (Binary Search)

 

[알고리즘] 매개변수 탐색(Parametric Search)

해당문제는 이분탐색과 매개변수탐색을 활용하여 푸는 문제였다. 해당 개념에 대한 조사는 구글링을 통해 하였고, 그 중에서 이해하기쉽게 설명한 사이트가 있어서 해당 사이트에서 개념을 확인한 후 문제를 해결하였다. 추가적으로 시간절약을 위해 파이썬 heapq 패키지를 활용하여 정렬을 하였다. 자세한 문제풀이 방법과 코드는 아래와 같다.

1. 입력받은 값을 리스트에 저장한 후 heapq패키지를 활용하여 정렬하여 풀이에 사용할 리스트로 변환해준다.

2. start 값은 0으로, end값은 리스트의 마지막값에 +1해준 값으로 설정한다.

3. start값과 end변수의 mid변수로 설정하고, 재귀함수를 이용하여 반복해주는 함수를 만들고, 이전에 나왔던 값과 현재의 mid가 같으면 결과값을 리턴하게끔한다.

4. 결과값 산출을 한 후 출력해준다.

 

import heapq
N, K = map(int, input().split())
sample = []
for _ in range(N):
    heapq.heappush(sample, int(input()))
lines = []
for _ in range(N):
    lines.append(heapq.heappop(sample))
start = 0
end = lines[-1] + 1
value = 0
def check(lines, start, end, K, value):
    cnt = 0
    mid = int((start+end) / 2)
    for line in lines:
        cnt += (line // mid)
    if cnt >= K:
        if value == mid:
            return value
        else: 
            value = mid
            start = mid
            return check(lines, start, end , K, value)
    else:
        end = mid
        return check(lines, start, end, K, value)
    
print(check(lines, start, end, K, value))

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.