백준-이분탐색(2110 공유기 설치)

10 Jul 2020

문제

입력

---

문제 해설

이분탐색인지 재귀인지 헷갈리는 문제였다… 당연히 이분탐색으로밖에 못푸는 입력 범위였다. key 아이디어는 집이 있는 좌표를 정렬하는 것과 하한/상한값의 mid값을 통해서 처음 집부터 출발하여 mid값과 다음 집까지의 거리를 비교하면서 공유기의 갯수를 세주는 것이다. 코드는 다음과 같다.

N, C = list(map(int, input().split()))
home_list = [int(input()) for _ in range(N)]
home_list.sort()

#공유기2개 설치할 때는 양쪽으로 설치하는게 제일 멈
if C == 2:
    print(home_list[-1]-home_list[0])
#공유기3개 이상일 때
else:
    #상한/하한값
    left_value = 1
    right_value = home_list[-1]-home_list[0]
    #이분탐색 시작
    while True:
        mid = (left_value+right_value)//2
        cnt = 0
        start_idx = 0
        flag = 0
        while True:
            #현재 집과 다음집의 거리를 mid값과 비교해준다.
            for i in range(start_idx+1, N):
                diff = home_list[i] - home_list[start_idx]
                if diff >= mid:
                    cnt += 1
                    start_idx = i
                    break
                elif diff < mid and i == N-1:
                    start_idx = i
                    flag = 1
                    break
            if cnt ==0 or flag == 1:
                break
        if cnt + 1 < C:
            right_value = mid
        else: 
            left_value = mid
        
        if right_value-left_value == 1:
            break
    
    print(left_value)

문제를 풀 때 당황해하지 않고 푸는게 가장 중요하다. 풀기전에 문제에 대한 아이디에이션과 메모가 중요하다. 머릿속으로 하려니깐 잦은 실수가 발생한다ㅜ