[알고리즘 연습]-랜선 자르기(python)

1. 문제링크

[랜선 자르기] : https://www.acmicpc.net/problem/1654

2. 풀이 전 생각

풀이를 하기전에 문제의 핵심을 먼저 파악하려고 했다. 랜선의 최대 길이를 찾는 것인데 순차 탐색보다는 이분탐색이 더 효율적일것 같다고 생각했고 어떻게 적용할지 고민했던 것 같다.

3. 풀이

import sys
k, n = map(int, sys.stdin.readline().split())
line = []
result = 0

for i in range(k):
    r = int(sys.stdin.readline())
    line.append(r)

current_max = max(line)
current_min = 0
current_try = (current_min + current_max) // 2

while current_min <= current_max:
    current_sum = sum([j // current_try for j in line])

    if current_sum >= n:
        result = current_try
        current_min = current_try + 1
    elif current_sum < n:
        current_max = current_try - 1
    current_try = (current_min + current_max) // 2
print(result)

주어진 랜선을 리스트에 저장하고 알고리즘 수업때 배운 이분탐색을 적용하였다. 주어진 랜선중 가장 큰 값을 current_max 값으로 놓고 0을 current_min으로 둔 다음 중간값을 시도값으로 놓는다. 리스트안에 랜선 값들을 시도값으로 나눈다음 합하여 n과 비교해주었다. current_sum이 n보다 크거나 같다면 시도값이 결과값이 되고 최솟값을 시도값의 +1로 바꿔준다. (문제의 조건에서 n보다 많이 만드는것도 n개를 만드는 것에 포함되기 때문)
n보다 작다면 최대값을 시도값의 -1으로 수정하여 다시 탐색한다.

4. 풀이하면서 고민했던 점

탐색을 쓰지않고 해결할 수 있는 방법도 고민했고, 시도하면서 어떻게 효율적으로 풀이를 만들 수 있는지 생각을 많이 했던것 같다.

5. 문제를 풀고 난 소감

이번주 문제를 풀면서 고민도 많이하고, 좀 더 알고리즘과 친해진것 같아서 좋다.