마구간 정하기 (결정알고리즘, 이분탐색)

인프런 김태원님의 파이썬 알고리즘 문제풀이를 듣고 작성한 글입니다.

https://inf.run/Uiep

파이썬 알고리즘 문제풀이 (코딩테스트 대비) - 인프런 | 강의

후... 어렵다.

문제들이 다 비슷한데 머릿속 생각을 코드구현하기가 쉽지않아서

강의를 봤다.

#강의 풀이

def Count(len):
    cnt = 1
    ep = Line[0]
    for i in range(1, n):
        if Line[i]-ep >= len:
            cnt += 1
            ep = Line[i]
    return cnt

n, c = map(int, input().split())
Line = []
for _ in range(n):
    tmp = int(input())
    Line.append(tmp)
Line.sort()
lt = 1
rt = Line[n-1]
while lt <= rt:
    mid = (lt+rt)//2
    if Count(mid) >= c:
        res = mid
        lt = mid + 1
    else:
        rt = mid - 1

print(res)

lt 와 rt 는 마굿간 위치는 아니고
나올 수 있는 마굿간과 마굿간 사이의 최대 거리를 구하기 위한 변수이다.

예제를 보면 lt = 1, rt = 9가 되고 mid = 5 가 된다.
5가 현재 마굿간과 마굿간 사이 최대 거리라고 가정하고

def Count( ) 함수에서 for문을 돌면서
첫번째 마굿간 (1) 을 endPoint로 지정후
두번째 마굿간 (2) 에서 첫번째 마굿간 까지 거리 = 1이
5보다 크다면 다음 마굿간으로 선정하여 cnt += 1 을 하고
작다면, 패스한다.

범위를 보고 이분탐색을 떠올렸으나...
구현이 어려운것 같아서
백준에서 더 풀어봐야겠다.