문제 / 랜선 자르기 / Python 파이썬

 

문제 제목: 랜선 자르기 (이분 탐색)

랜선자르기(결정알고리즘) 엘리트 학원은 자체적으로 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줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의    이하의 자연수로 주어진다.

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

▣ 입력예제

4 11

802 743 457 539

▣ 출력예제 

200

 

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

---

 

모범답안

def Count(len):
    cnt=0
    for x in Line:
        cnt+=(x//len) # x(Line의 랜선)를 len으로 나누어서 나오는 값 
    return cnt

k, n=map(int, input().split()) # 가진 랜선 개수: K개, 만들고자하는 랜선의 수: n개
Line=[] 
res=0
largest=0 
for i in range(k):
    tmp=int(input()) # 입력받은 랜선의 길이
    Line.append(tmp) # 리스트로 추가하기
    largest=max(largest, tmp) # 길이가 가장 긴 랜선
lt=1 # 이분탐색 왼쪽 시작지점
rt=largest # 이분탐색 오른쪽 시작지점
while lt<=rt: # lt와 rt가 같거나 lt가 rt보다 오른쪽으로 가면 끝낸다.
    mid=(lt+rt)//2 # 중간지점
    if Count(mid)>=n: 
    # Count 함수에서 mid값을 인자로 넣고 반환된 값과 n(만들고자하는 랜선의 수)비교
    # Count 함수로 반환된 값이 n보다 크거나 같을 경우 lt를 1씩 증가함
    # (lt와 rt의 중간인 mid의 값이 최댓값을 구해야하므로 lt가 커지면 mid값도 증가)
        res=mid 
        lt=mid+1 
    else:
    # 해당 구간에서 만들고자하는 랜선의 수보다 cnt가 작으므로 rt를 줄여줌
        rt=mid-1 
print(res)

가장 긴 랜선의 길이를 구해야하는 이유:

이분 탐색으로 해당 랜선의 길이만큼의 범위를 lt와 rt를 이용해서 적절한 해를 찾아나가야하기 때문

 

예를들어서 입력예제에서 가장 큰 수가 802 이므로

1~802 까지에서 중간 길이 mid를 설정하고

lt와 rt의 구간을 조절해가며 mid값을 조정한다.

구간을 조정하면서 만들어야하는 랜선의 수가 N이고,  길이가 최대가 되면 해당 길이 값을 반환

---