[코딩테스트] 2. 랜선 자르기(결정 알고리즘)

문제

K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다.

N개의 같은 길이의 랜선으로 만들고 K개의 랜선을 잘라서 만들어야 한다.

 

Ex. 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야한다.

 

기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 하자.

그리고 자를 때는 항상 센티미터 단위로 정수 길이만큼 자른다고 가정하자.

N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다.

이때 만들 수 있는  최대 랜선의 길이를 구하는 프로그램을 작성하시오.

 

입력설명

첫째 줄에는 엘리트 학원이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1 이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K <=N이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터, 단위의 정수로 입력된다.

 

출력설명

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

 

입력 예제

4 11 -> 4개의 랜선이 있는데 11개의 랜선을 만들 때, 각각 하나의 길이를 최대 몇으로  해야 하는가.

802 : N개의 랜선 1개의 길이 1 ~ 802 사이의 값일 것.

743

457

539

 

출력예제 1

200

 

처음범위 : 1~ 1000

중간 값 500  : 500 이라는 N개의 랜선이 나오는 가.

802에서 500을 갖는 랜선이 몇 개 나오는 가. 800//500 -> 1개만이..

743//500 -> 1개만이... 457// -> 1개만이 =>> 500은 답이 되지 않음

 

두번째 범위 1~499

중간 값:  250 : 250이 답이 되는 가 ? count 시작

802 -> 3개 743 -> 2개 457 -> 1개 539 -> 2개 --> 11개 이상이 나오지 않았음 -> 250 또 안됨

 

세번째 범위 1~249

중간 값: 125 : 125가 답이 되는 가? 

802 -> 6, 743 -> 5, 457 -> 3, 539 -> 3 --> 18개 나옴 -> 되긴 함. 우선 답이 되긴 함. res= 125 정답 저장.

 

네번째 범위 126~249

중간 값: 187 : 187 답이 되는 가?

802 -> 4개, 743 -> 3개, 457 -> 2개, 539 -> 2개 -> 되긴 함. 답이 됨 -> res=187 정답  저장.

당연히 다음에 나온 값이 좋은 값이 됨

 

계속 ... 이분 검색 하다 보면, 가장 좋은 답이 나중에 나옴

 

코드

import sys

sys.stdin = open('input.txt','r')

def Count(len):
    cnt = 0
    for x in Line:
        cnt += (x//len) # N개의 랜선을 만들면 cnt에 누적.
    return cnt
    
n, m = map(int, input().split())

Line = []
largest = 0

res = 0 #  최댓값을 찾아야함, 줄바꿈으로 들어오는 건 하나하나 읽어야 함.

for i in range(k):
    tmp = int(input()) # 1개의 숫자를 읽는 것.
    Line.append(tmp) # Line이라는 리스트에 추가가 됨
    largest=max(largest,tmp)

lt=1
rt=largest

while lt<=rt:
    mid=(lt+rt)//2 # 한 개 랜선의 길이. 그것의 중앙값 => 랜선의 길이
    if Count(mid)>=n: # 만들어 낼 수 있는 개수가 N보다 크면 조건 만족
        res=mid # 더 좋은 범위로 만들어줘야만.
        lt=mid+1
    else:
        rt=mid-1

#최적의 답을 찾아 res에 넣었을 것.

print(res)