백준 1642번 - 랜선 자르기 - 파이썬(Python)

문제 링크

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

문제

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 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

 

 

풀이 전 생각

2025.02.14 - [알고리즘/24-25 겨울 코딩테스트 스터디] - 백준 2110번 - 공유기 설치 - 파이썬(Python)

백준 2110번 - 공유기 설치 - 파이썬(Python)

 이 문제와 유사한 방식으로 풀면 될 것 같다는 생각이 들었다.

2110번에서는 이진 탐색할 대상을 공유기 사이의 거리로 설정했고 조건을 만족하는 곳에 공유기를 모두 설치하고, 이후에 설치하고자 하는 공유기의 개수와 비교했을 때 더 많이 설치되었다면 최소 거리를 늘려서 개수를 줄였고, 더 적게 설치되었다면 최대거리를 줄여서 개수를 늘리며 설치하고자 하는 공유기의 개수에 맞는 최대거리를 찾을 수 있었다.

 

이번 문제에서도 원리는 같을 것 같다. 이진 탐색할 대상은 '만들 수 있는 랜선의 최대 길이'로 설정하고, 이진 탐색을 진행하며 입력받은 각 랜선에서 만들 수 있는 랜선의 수를 count해주고, 만들고자 하는 랜선의 길이보다 많이 만들어졌다면 최소 길이를 늘리고, 적게 만들어졌다면 최대길이를 줄여 만들고자 하는 랜선의 개수만큼 만들어주면 될 것 같다. 다만 2110번과의 차이점은 최대거리를 설정할 때 arr[-1]-arr[0]이 아닌 랜선 중 가장 길이가 짧은 것을 선택해주어야 할 것 같다. 라고 생각을 했는데, 코드를 완성하고 반례를 찾을 수가 없어서 테스트케이스를 돌려보니

5 5
12
13
3
5
11

 

이런 식으로 입력받을 경우에, 사용되지 않는 랜선이 있을 수도 있다는 점을 고려하지 못했다. 따라서 최대거리를 '랜선 중 가장 길이가 긴 것'으로 수정하고 문제를 해결할 수 있었다.

 

예제 코드

def binary_search(start,end,c):
    while start <= end:
        mid = (start+end)//2
        num = 0
        for i in range(len(lan)):
            num = num + lan[i]//mid
        if num < c:
            end = mid - 1
        else:
            start = mid + 1
    print(end)
        

k,c = map(int,input().split())

lan = []
for _ in range(k):
    lan.append(int(input()))

lan.sort()
start = 1
end = max(lan)
binary_search(start,end,c)

 

 

생각

이번 문제는 이진 탐색과 관련된 문제였는데, 앞선 DFS,BFS 와 유사하게 쓰이는 알고리즘이 같은 문제들은 코드 작성 방식이 거의 유사한  것 같다. 하지만 스스로 나름의 규칙을 정해두지 않고 매번 문제를 풀 때마다 보니 헷갈리는 부분도 자주 생기고 디버깅하는 시간도 생각보다 오래 걸리게 된 것 같다. 그래서 이진탐색과 관련해 조금 일관성있게 정리를 해보려고 한다. 

 

이진 탐색 코드 작성 시 헷갈릴 수 있는 부분 

보통 left, right, mid(이번 문제에서는 start,end,mid) 를 설정하고 while 문을 사용하여 이진탐색을 진행하게 되는데 

 

1. while문의 조건을 start<end 로 설정할지, start<=end 로 설정할지

 

범위를 줄여줄 때

 

2. end = mid 로 해야할지, end = mid -1 로 해야할지

3. start = mid 로 해야할지, start = mid + 1 로 해야할지

 

그리고

 

4.최종적으로 답안 출력을 start,mid,end 중 어느 것으로 할지

 

upper bound

https://www.acmicpc.net/blog/view/109

 

 

 

 

parametric search

https://ialy1595.github.io/post/parametric-search/

파라매트릭 서치 (Parametric Search) | ialy's blog