[이분탐색(결정알고리즘)][그리디 알고리즘] - 랜선 자르기(결정 알고리즘)

<결정 알고리즘를 푸는 팁>

해당 알고리즘의 경우엔 답이 쉽게 보이며 이를 범위를 줄여가며 해당 답을 찾는 문제가 대다수이다.

 

문제

• k개의 랜선들을 n개의 랜선으로 잘라야한다. 
• n개보다 많이 만드는 경우는 n개를 만드는 경우에 포함된다.
• 이때 해당 n개의 개수만큼 만들 수 있는 최대 랜선의 길이를 구하라 

문제 풀이 - 1

#랜선자르기(결정 알고리즘)
k, n = map(int,input().split())
a = [int(input()) for _ in range(k)]
lt = 1
rt = max(a)
res = 0

while lt <= rt:
    mid = (lt+rt)//2
    s = 0
    for i in a:
        s += i//mid
    if s >= n:
        res = mid
        lt = mid + 1
    else:
        rt = mid -1
        
print(res)

• 이 경우 최대 값이 입력값의 최대수로 두면 된다.
• s의 경우엔 해당 값을 mid가 바뀔때마다 사용해야 하기에 for문 들어가기 전에 초기화 해준다!
• s 값이 원하는 랜선 값보다 적은 수로 나오는 경우엔 rt 값을 옮겨 더 작은 값으로 나누며 진행한다. (더 작은 값을 이용해 나누어야 랜선이 더 많이 나오기 때문이다)
• s = 자른 랜선 갯수의 합이 우리가 가지고 싶은 랜선의 개수 n개보다 많거나 같을 땐 해당 mid(값을 이용해 나누었음)을 계속해서 비교해 res 값에 저장해준다. (최대 랜선값을 구해야 하기 때문에 lt 값이 커지면 랜선 갯수는 원하는 만큼 얻고 랜선 길이는 최대를 구할 수 있기 때문이다!)

문제 풀이 - 2 

def Count(len):
    #해당 길이로 만들 수 있는 랜선 갯수
    cnt = 0
    for x in a:
        cnt += (x//len)
    return cnt

k, n = map(int,input().split())
a = [int(input()) for _ in range(k)]
lt = 1
rt = max(a)
res = 0


while lt <= rt:
    mid = (lt + rt)//2
    if Count(mid)>= n:
        res = mid
        lt = mid + 1
    else:
        rt = mid -1
        
print(res)

• 위의 문제 풀이와 똑같은 매커니즘이지만 Count부분을 for문으로 직접 돌리던 것과 다르게 함수로 만들어서 사용했다는 점이 다르다.