💡문제 분석 요약

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

• 길이가 제각각인 K개의 랜선을 모두 N개의 같은 길이의 랜선으로 만들려고 한다.
• 이미 자른 랜선은 붙일 수 없다.
• ex. 300cm 랜선에서 140cm 랜선을 두 개 잘라내면 20cm는 버려야 함
• 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없음
• 자를 때는 정수길이 단위
• N개보다 많이 만든느 것도 N개를 만드는 것에 포함함
• 만들 수 있는 최대 랜선의 길이 return

💡 K = 4 N = 11
802
743
457
539
최대 랜선의 길이가 200일 때
802cm 랜선에서 4개, 743cm 랜선에서 3개, 457cm 랜선에서 2개, 539cm 랜선에서 2개를 잘라내 모두 11개를 만들 수 있음

💡알고리즘 설계

• 입력받은 랜선의 길이를 LAN 변수에 list로 저장 후 start = 1, end = min(LAN)
• 해당 구간을 이진탐색 하며 LAN의 각 요소를 mid로 나눈 몫 확인
  • 몫의 합이 N의 값보다 크거나 같다면 start = mid + 1
  • N보다 작다면 end = mid - 1
• end return

💡코드

import sys

def CUTLAN(n, lan) :
    start = 1
    end = max(lan)

    while start <= end :
        mid = (start + end) // 2
        sum = 0
        for l in lan :
            sum += l // mid
        if sum >= n : start = mid + 1
        else : end = mid - 1
    return end

if __name__ == '__main__' :
    k, n = map(int, sys.stdin.readline().split())
    lan = []
    for i in range(k) :
        lan.append(int(sys.stdin.readline()))
    print(CUTLAN(n, lan))

💡시간복잡도

• 1부터 N까지 이진탐색하므로 O(logN)
• 위 loop 안에서 LAN길이(M)만큼 for loop를 돌기 때문에 O(M)
• 따라서 시간복잡도는 O(MlogN)

💡 틀린 이유

• k = 3, n = 4, 10 10 1 로 입력이 들어왔을 때를 처리하지 못함

💡 틀린 부분 수정 / 다른 풀이

• end의 값을 LAN의 min 값으로 해도 된다고 생각했는데 위의 경우 start = 1, end = 1이 되어 결과값이 예상했던 5가 아닌 1이 나온다.

💡 느낀점 / 기억할정보

• end의 값을 반례를 생각하며 조금 더 꼼꼼하게 정하도록 하자
• 마지막에 return end를 하는 이유는 while루프를 빠져나올 때 end의 값이 바뀌면서 나오기 때문인 것 같다.