1654 랜선 자르기

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

import sys
read = sys.stdin.readline

K,N = map(int,read().split())
length_array = [0]*K

for i in range(K):
    length_array[i] = int(read())
start = 1
end = max(length_array)

while (start<=end) :
    length = (start + end) // 2
    cnt = 0
    for j in range(K):
        cnt += length_array[j] // length # 랜선 자르고 개수 더하기
    # print("start : {} end : {} length : {} cnt : {} N : {}".format(start,end,length,cnt,N))
    if cnt >= N : start = length +1
    else :  end = length-1
print(end)

3. 문제 풀이

이것도 일종의 자르기 문제로써 이진탐색의 변형인데, 사실 아직 좀 이해가 안간다. 좀더 문제를 풀어보면서 감을 익혀야할 것 같다.

문제를 보면 개수를 N보다 크게 만드는 것을 포함한다고 하니 적어도 N개 이상을 만들라는 이야기다. 그래서 문제를 보면 N이 딱 얼마일때 끝내는게 아니라, N개이상의 랜선들이 만들어 질 때, 최대 랜선의 길이를 구하는 것이므로 start와 end가 엇갈리때까지 계속 보는거 같은데.. 이게 엇갈리더라도 N개 이상이 안나오는 반례가 뭔가 있을 것 같은데.. 잘 모르겠다 아직은.