[백준] 1654번 랜선 자르기(파라메트릭 서치)(Python - 파이썬)

백준 1654번 랜선 자르기 문제입니다. (solved.ac)기준 실버 3 문제입니다.

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

힌트 :
802cm 랜선에서 4개, 743cm 랜선에서 3개, 457cm 랜선에서 2개, 539cm 랜선에서 2개를 잘라내 모두 11개를 만들 수 있다.

이미 가지고 있는 랜선의 개수 K와 필요한 랜선의 개수 N을 입력 받는다. (1 <= k <= 10,000), ( 1 <= N <= 1,000,000), (K <= N)

그 후 K 줄에 걸쳐 이미 가지고 있는 랜선의 개수(K)만큼 랜선의 길이를 입력 받는다. 

 단, N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다.

 주어진 범위 내에서(가지고 있는 랜선의 길이) 원하는 조건(N개를 만들 수 있는 랜선의 최대길이)를 구하는 문제이기 때문에 파라메트릭 서치(Parametric Search)로 접근하여 문제를 해결하였습니다.

정답 코드

# 랜선 자르기

import sys

# k는 이미 가지고 있는 랜선의 수
# n은 필요한 랜선의 수
k, n = map(int, sys.stdin.readline().rstrip().split())
line = []

# 가지고있는 랜선의 길이를 입력 받음
for _ in range(k):
    line.append(int(sys.stdin.readline().rstrip()))

# 파라메트릭 서치를 하기위하여 오름차순으로 정렬
line.sort()

# 랜선의 최소 길이
start = 1
# 랜선의 최대 길이
end = max(line)
# 결과를 담을 변수
result = 0

# 랜선의 길이를 파라메트릭 서치하여 만들 수 있는 최대길이를 구함.
# strat가 end보다 커질때 까지 탐색
while (start <= end):

    # count는 만들어진 랜선의 개수
    count = 0
    # 최대 랜선의 길이(파라메트릭 서치중이므로 중간값)
    mid = (start + end) // 2

    # 주어진 랜선길이들과 mid를 순차적으로 비교하여
    # mid보다 x가 더 크다면 x // mid를 count에 넣어줌
    # ex) mid가 200일 때 802 // 200 = 4 이기때문에
    # count += 4가 됨
    # 802는 길이가 200인 랜선 4개가 만들어 진다는 뜻
    for x in line:
        if x >= mid:
            count += x // mid

    # 만들어야할 랜선의 개수(n)보다 만들어진 랜선의 개수(count)
    # 가 작다면 랜선의 길이를 줄여야 하므로
    # end를 mid-1로하고 다시 탐색(다음 mid 감소)
    if count < n:
        end = mid - 1
    # 만들어야할 랜선의 개수(n)보다 만들어진 랜선의 개수(count)
    # 가 크거나 같다면 최대 랜선의 길이(mid)를 정답값(result)에 넣고
    # 랜선의 길이를 늘려야 하므로
    # start를 mid+1로하고 다시 탐색(다음 mid 증가)
    else:
        result = mid
        start = mid + 1

print(result)

비슷한 유형의 문제들

[백준] 2805번 나무 자르기(파라메트릭 서치(Python)

[백준] 2805번 나무 자르기(파라메트릭 서치(Python)

[백준] 2110번 공유기(파라메트릭 서치)(Python)

[백준] 2110번 공유기(파라메트릭 써치)(Python)

[백준] 2512번 예산(파라메트릭 서치)(Python)

[백준] 2512번 예산(파라메트릭 써치)(Python)