[Algorithm] 백준 #2110 공유기 설치 + 이것이 취업을 위한 코딩테스트다.

https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

0. 에필로그

이코테 책에 있는 문제 푸는 중..와중에 백준 골드라 더 하기 싫었다. 아무리 고민해 봐도 모르겠는 문제는 고민을 포기하고 답을 찾게 된다. 사실상 문제 자체도 이해하기가 어려웠다. 점점 바보가 되는 것 같은 건 기분 탓이겠지. 너무 꼴 보기가 싫어서 이틀에 나눠서 정리했다.

결론적으로 어떤 값을 구해야하는지를 고민했다. 입력값 자체가 집의 x좌표이기에 오히려 쉽다는 생각을 했는데, C만큼 공유기를 설치할 때 가장 인접한 두 공유기 간의 거리의 최댓값을 구하면 된다. 생각하다가 x좌표가 집이 있는 곳인지 그냥 좌표인지 수 없이 헷갈리기에 집이라는 표현은 하지 않았다. 좌표==집

집의 좌표가 1, 2, 4, 8, 9이고 공유기를 1, 8, 9에 공유기를 설치하면 8, 9로 1이 되므로 더 커질 수 있는 경우를 생각해야 한다.

1, 4, 8이나 1, 4, 9에 설치한다면 가장 인접한 두 공유기 사이의 거리는 3으로 최대가 된다. 

 

1.  간단한 개념

찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 게 이진 탐색 과정이다.
p.188

이진 탐색은 범위를 반으로 자르고 찾고, 범위를 반으로 자르고 찾고 반복한다. 내부 데이터가 정렬되어 있어야 하며 시작점, 끝점 중간점으로 변수를 나눠 탐색한다. 코테에서 이진 탐색은 단골이기에 가급적 외우고자 한다. 난이도가 더 올라가면 그리디랑 이진 탐색을 모두 사용해서 풀어야 하는 문제도 나온다 ㅠㅠ

 

2. 풀이

이때 각 집의 좌표가 최대 10억이므로, 이진 탐색을 이용해야 한다. 

문제에서 가장 인접한 두 공유기 간의 거리의 최댓값을 구하면 되고 가능한 최소 거리는 1, 최대 거리는 마지막 값-처음 값이다.

즉, 최대 거리를 반으로 잘라서 탐색하고 C만큼 설치할 수 있는지 조건을 걸면 된다. 그러나 가장 인접한 두 공유기 사이의 거리의 최댓값을 찾아야 하므로 C보다 많이 설치할 수 있다면 거리를 증가시켜 더 큰 값에서도 성립하는지 확인한다. 두 공유기 사이의 거리를 증가시켰을 때 C개 이상을 설치할 수 있으면 start 값을 증가시키고 else이면 거리를 줄여야 하므로 end 값을 감소한다.

- 7장 떡볶이 떡 만들기 문제와 유사

- 파라메트릭 서치 유형

 

Step1

집의 좌표 [1, 2, 4, 8, 9]

최대 gap=8

최소 gap=1

범위 : [1, 8]

gap(=mid, 중앙값) = 4

1+4 =5 인 5보다 큰 8에 설치 가능

2개밖에 설치 못하므로 (여기가 else의 경우) 범위의 end 값을 mid-1로 변경한다. 

 

Step2

범위 : [1, 3]

gap(=mid, 중앙값) = 2

• 1+2=3 보다 큰 4에 설치 가능
• 4+2=6 보다 큰 8에 설치 가능
• 8+2=10 은 집이 없어서 패스

3개 설치 가능하지만 gap이 더 커졌을 때도 가능한지 비교해봐야 한다.

 

Step3

범위 : [3, 3]

gap(=mid, 중앙값) = 3

위와 같은 방법으로 3개 설치 가능하고, gap이 더 커졌을 때도 가능한지 비교해보려고 했지만, 범위가 이미 [3,3]이라 더 이상의 범위 변경은 불가능하다. 따라서 gap=3이 print 된다. 

 

  3. 코드

# 가장 인접한 두 공유기 사이의 거리를 최대로 만들기
n, c = map(int, input().split())

array = [] # 집의 좌표 저장할 리스트 초기화

# 각 집의 좌표 입력 >> 오름차순 정렬 - 정렬되어 있는 값만 이분탐색 가능
for _ in range(n):
    array.append(int(input()))
array.sort() 

start = 1 # 거리의 최솟값
end = array[-1] - array[0]  # 거리의 최댓값(첫 번째 집과 마지막 집 사이의 거리)
result = 0 # 가장 인접한 두 공유기 사이의 최대 거리를 저장

# 거리의 최소값과 최대값을 조정하며 탐색
while(start <= end):
    mid = (start + end) // 2  # 현재 탐색하는 거리의 중간
    value = array[0] #현재 거리로 공유기를 설치할 때, 마지막으로 공유기를 설치한 집의 좌표를 저장
    count = 1 # 설치한 공유기의 개수
	
    # 현재의 mid값을 이용해 공유기를 설치
    for i in range(1, n):
        if array[i] >= value + mid: # 현재 집과 이전에 설치한 집 사이의 거리가 현재 거리 이상이면
            value = array[i] # 현재 집을 마지막으로 설치한 집
            count += 1 
    if count >= c:  # 현재 거리로 설치한 공유기의 개수가 목표 개수 c보다 크거나 같다면,
        start = mid + 1 # 거리의 최소값을 증가시켜 더 멀리 떨어진 공유기를 설치
        result = mid # 가장 인접한 두 공유기 사이의 최대 거리를 result에 저장
    else:  # c개 이상의 공유기를 설치할 수 없는 경우, 거리를 감소
        end = mid - 1

print(result)

+ 가장 인접한 두 공유기 간의 거리의 최댓값=mid=gap=result

결론적으로 다 같은 말인데, 쓰다보니까 뭐 이렇게 나눠졌는지 의문이다.