3. 백준 Python[1654] 랜선 자르기

[1654] 랜선 자르기

---

 

난이도: Silver 3

시도횟수: 2

www.acmicpc.net/problem/1654

문제

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.

이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)

편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

 

---

제출한 코드(1) - 시간초과

import sys

N, K = map(int, sys.stdin.readline().split())
LAN_sun=[]
for i in range(0, N):
    LAN_sun.append(int(sys.stdin.readline()[:-1]))

start=max(LAN_sun)

while True:
    hap=0
    for line in LAN_sun:
        hap+=line//start
    if hap>=K:
        print(start)
        break
    else:
        start-=1

알고리즘 기초가 전혀 없어서 처음에는 가장 긴 랜선의 길이에서 1씩 줄여가며 k개 이상의 랜선이 나올 때 자른 길이를 출력하도록 했습니다. 문제는 이렇게 하면 시간복잡도가 O(N^2)이라서 1초안에 해결이 안됩니다. 이렇게 푸는걸 선형탐색(linear search)이라고 한다고 하네요

---

제출한 코드(2)

import sys

N, K = map(int, sys.stdin.readline().split())
LAN_sun=[]
for i in range(0, N):
    LAN_sun.append(int(sys.stdin.readline()[:-1]))

maximum=max(LAN_sun)
minimum=0
answer=0
while maximum>=minimum:
    hap=0

    mid=(maximum+minimum)//2
    if mid==0:
        answer=1
        break
    for line in LAN_sun:
        hap+=(line//mid)
    if hap<K:
            maximum=mid-1
    else:
        minimum=mid+1
        if answer>=mid:
            continue
        else:
            answer=mid

print(answer)

이 문제는 이진탐색(binary search)으로 풀어야한다고 합니다. 시간복잡도가 O(NlogN)까지 줄어들어 제한시간 내에 해결이 가능합니다. 자연수나 이미 sort된 자료에서 앞으로 유용하게 쓸 것 같습니다.