1654. 랜선 자르기 (파이썬) | 이분 탐색 | 매개변수 탐색

문제

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

 

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

 

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

입력

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다.

출력

첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

예제

입력

4 11
802
743
457
539

출력

200

힌트

802cm 랜선에서 4개, 743cm 랜선에서 3개, 457cm 랜선에서 2개, 539cm 랜선에서 2개를 잘라내 모두 11개를 만들 수 있다.

최종 답:

import sys
K, N = map(int,input().split())

lenarr= [int(sys.stdin.readline().rstrip()) for _ in range(K)]

start=0
end = max(lenarr)

def check(cuttinglength):
    sum = 0

    for lenline in lenarr:

        result = lenline//cuttinglength
        sum += result

    if (sum >= N):
        return True
    else:
        return False


while (start <= end):

    mid = (start + end) // 2

    if (check(mid)==True): 
        start = mid+1
    else:
        end = mid -1

print(end)

문제풀이

이 문제는 이분탐색, 매개변수 탐색이라는 알고리즘을 알아야 풀 수 있는 문제다. 이 알고리즘을 몰라도 답은 나오지만, 아마도 백준 사이트에 제출하면 시간초과가 뜨면서 실패하게 된다.

이분탐색을 위해서는 랜선을 만들 수 있는 최솟값과 최댓값을 먼저 설정해야 한다.

오영식이 가지고 있는 랜선의 최소길이는 0이다. 문제에서 랜선의 길이는 센티미터 단위의 정수라고 했기 때문이다.

 

최대길이는 오영식이 가지고 있는 랜선들 중 가장 길이가 긴 것이 될 것이다. 예제를 예로 들면 영식이가 가지고 있는 4개의 랜선의 길이 802, 743, 457, 539 중 가장 긴 802가 될 것이다.

 

그러면 1과 802 중에서 잘라진 랜선의 개수가 11개인 숫자를 찾으면 된다. 그런데 802까지 찾기에는 숫자가 너무 크니, 이때 이분탐색이라는 알고리즘을 쓰겠다는 얘기다.

 

먼저 0과 802 의 중간값은 401이 된다. 401의 경우 자를 수 있는 랜선의 개수의 합(\sum\)는

(802/401) + (743/401) + (457/401) + (539/401) = 5 이다.

 

잘라야 하는 랜선의 개수 11보다 작으니 답은 0과 401사이에 있다. (end값을 401로 바꾸어 준다)

다시 0과 401 중간값인 200을 찾는다. 이때 자를 수 있는 랜선의 개수는 4+3+2+2=11 이 된다. 어! 잘라야 하는 랜선의 개수(N)과 숫자가 같으니 이게 답일까? 그렇지 않다. 이 문제는 잘라야 하는 랜선의 개수를 만족하면서 랜선 길이의 최대값도 만족해야 하기 때문이다. 예를 들어 200cm도 11개로 자를 수 있고 205cm도 11개로 자를 수 있다면 205가 답이라는 얘기다. 그러니 200부터 401사이의 값도 다 일일히 확인해 주어야 한다.

 

이런 식으로 start와 end 값을 조절해가면서 답을 찾아가면 된다.

답이 되는 순간은 start와 end값이 같아지는 순간이다.

Troubleshooting

이 문제가 풀기 까다로운 이유는 에러가 많이 나기 때문이다. 내가 겪은 에러를 정리해 적어두니 참고하면 좋겠다.

 

• start와 end값을 바꿀 때 왜 +1과 -1을 각각 빼는 이유

if (check(mid)==True): 
        start = mid+1
    else:
        end = mid -1

 

end값은 check함수에서 False가 나왔을 때 바꾸게 된다. 즉, N보다 sum이 작을 때다. 어차피 이 mid값으로는 원하는 만큼의 랜선의 개수를 만들 수 없다. 그러니 1을 빼주는 것이다.

start값에서 1을 더해주는 이유는 마지막 값을 구할 때 있다.

 

 

이 값은 위 예시에서 while문이 돌 때마다 start값과 end값을 출력한 것이다. 맨 마지막에 보면 start > end 이다. 그래서 while문의 조건 (start <=end)를 만족하지 못하면서 end값, 즉 답이 출력되는 것이다.

 

만약 mid+1을 하지 않으면 어떻게 될까?

start는 200, end는 201에서 mid값은 200이 되어 check함수에서 계속해서 True를 생산하면서 while문을 빠져나오지 못하고 무한루프를 돌게 된다.

 

 

이를 해결할 방법은 없을까? 나는 if문을 추가해줘서 mid값과 start값이 같다면 루프를 빠져나올 수 있도록 했고 답도 나왔지만 백준에서는 답으로 인정되지 않았다. 이 부분은 아직도 잘 모르겠다. 혹시 이유를 안다면 댓글로 알려주시면 감사하겠다.

 

• 시간초과

많이들 시간초과가 나서 정답인정이 안 되는 것 같다. 이유는 첫번째, 이분탐색이라는 알고리즘을 적절히 사용하지 못해서일 수도 있고 나는 이진탐색을 썼는데도 시간초과가 났다.

 

이를 해결하려고 lenarr을 받을 때 for문을 간단히 바꾸었고 lenarr을 입력받을 때도 입력과 for문을 한 줄에 쓰니 정답처리가 되었다. 허무하지만 안 되는 분은 코드를 한번 간단히 바꿔보라.

 

• 최댓값을 설정하는 문제

최댓값을 이렇게 설정하는 또 다른 방법도 있다.

end=sum(lenarr)//N

 

804라는 숫자가 너무 크고 답이 될 가능성이 없으니, 답은 오영식이 가지고 있는 모든 랜선의 개수를 잘라야 하는 랜선의 길이만큼 나눈 숫자보다 작은 수 중에 있을 것이기 때문이다.

 

 

 

*완성된 코드는 깃허브에 올려두었습니다.

 

 

 

참고 블로그

이분탐색: https://velog.io/@guswns3371/%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%EB%A7%A4%EA%B0%9C-%EB%B3%80%EC%88%98-%ED%83%90%EC%83%89

매개변수 탐색: https://kosaf04pyh.tistory.com/95