[BOJ 1654] 랜선 자르기(Python)

문제링크

랜선 자르기

풀이 전 계획 및 생각

자를 수 있는 최대 길이를 찾아야해서 완전 탐색을 해보려했다.
가장 작은 값부터 가장 큰 값까지 길이를 하나씩 증가시키는 알고리즘을 가장 먼저 떠올렸고, 그 연산을 더 빠르게 할 수 있는 방법을 생각하면서 binary search를 이용하기로 결정했다.

while문을 이용하면서 현재 자르려고 하는 길이로 만들 수 있는 개수를 계산해본다.
그리고 그만큼 자를 수 있는 길이를 찾았더라도 그것보다 더 긴 길이로 n개를 만들 수 있는 경우가 있을 수 있어서 n개로 자를 수 있는 경우를 찾더라도 이진 탐색을 끝까지해줬다.

풀이

import sys
k, n = map(int, sys.stdin.readline().split())
array = []
total = 0
for _ in range(k):
    l = int(sys.stdin.readline())
    array.append(l)
    total += l
avg = int(total / n) + 1

start = 0
end = avg
ans = 0
while 1:
    count = 0
    ans = (start + end) // 2
    for data in array:
        count += data // ans
    if end - 1 <= start:
        break
    elif count == n:
        start = ans
    elif count < n:
        end = ans
    elif count > n:
        start = ans

print(start)

풀이하면서 막혔던 점과 고민했던 점

처음에 이진 탐색을 떠올린 후에, count == n일 때, break을 걸어줬었다.
그대로 제출을 했더니 오답이 나왔다.
찾은 값이 가장 큰 값이 아닐지도 모르는데, 가장 먼저 나온 값이라해서 최대가 아닐 수 있다는 것을 간과했었다.

풀이 후 알게된 개념과 소감

최대값, 최소값 등등 모든 경우의 수를 다 봐야지 알 수 있는 것들은 특정 값이 최대값이라고 수식화할 수 있는게 아니면 끝까지 해보는게 좋겠다는 생각을 했다.