백준 알고리즘 - 랜선 자르기 (1654) [Python]

 

 

 문제

 

www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

 

 

 

 

 

 문제 상황

 

- 입력받은 개수 N만큼 자른 랜선을 만들어야 할 때, 최대의 길이로 랜선을 자를 때 그 최대 길이를 계산한다.

 

 

 

 

 

 

 해결 전략

 

- 방법은 두가지로 나눌 수 있다. 

 

    1) 길이를 정해 개수를 계산

    2) 개수를 정해 길이를 계산

 

   2번의 경우 개수가 정확히 N개일 때면 가능하지만 N보다 크거나 같다는 상황이므로 2번보단 1번의 방법이 유리하다. 길이의 경우 단순히 완전탐색하는 것이 아니라 이분 탐색을 통해 검색할 범위를 줄여준다.

 

 

 

 

 

 

 코드

 

from sys import stdin
input = stdin.readline
K, N = map(int, input().split())
K_list = [int(input()) for _ in range(K)]
K_list.sort()
min_len = 0 
max_len = K_list[-1]
mid = max_len
def cutting(K_list, length, N):
    cnt = 0
    for i in range(len(K_list)):
        cnt += (K_list[i]//length)
    if cnt >= N : return True
    return False
while True:
    mid = ((min_len+max_len)//2)
    if max_len == 1:
       print(1) if cutting(K_list, max_len, N) else print(0)
       break
    elif max_len == 0:
        print(0)
        break
    if cutting(K_list, mid, N):
        min_len = mid
    else :
        max_len = mid
    if max_len-min_len <= 1 :
        print(max_len) if cutting(K_list, max_len, N) else print(min_len)
        break

 

 

 

 

 

 

 

 

 해설

 

- 0부터 최대 길이를 기준으로 이분탐색하며 길이를 검색하고, 그 길이가 가능한지 여부를 cutting 함수를 통해 판단한다. cutting이 가능하면 다시 그 조건을 base로 놓고 다시 연산하고, 불가능하면 ceiling으로 선언하여 다시 연산을 반복한다. 연산이 종료되는 조건은 min과 max의 차이가 1 이하인 경우인데, 같다는 조건을 사용하면 무한 루프에 빠지는 경우가 발생한다. 그래서 1차이 날 때에, max가 가능한지 여부를 통해 출력 내용을 결정한다. 

 

 

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- 99%에서 런타임 에러가 발생하였다. 런타임 에러가 발생하는 경우를 기존에는 index 에러로만 생각했는데 분모가 0인 경우도 런타임 에러가 발생함을 알았다. 

 

- 조건을 조금 더 깔끔하게 줄 수 있을 것 같은데 우선 직관적으로 생각나는 방법으로 오류를 처리하였다.