1. 개요
문제 링크: https://www.acmicpc.net/problem/2110
2. 코드
def solve(c):
global arr
right_val = arr[-1] - arr[0] + 1
left_val = 1
mid_val = 0
max_len = -1
while left_val < right_val:
mid_val = (right_val + left_val) // 2
count = 1
crit_idx = 0
for i in range(1,len(arr)):
if arr[i] - arr[crit_idx] < mid_val:
continue
else:
count += 1
crit_idx = i
if count > c: # count가 너무 크다 = 집거리가 너무 짧다
max_len = max(max_len, mid_val)
left_val = mid_val + 1
elif count == c: # count가 같다 = 더 큰 값도 가능한가?
max_len = max(max_len, mid_val)
left_val = mid_val + 1
elif count < c: # count가 너무 작다 = 집거리가 너무 길다
right_val = mid_val
return max_len
n, c = list(map(int,input().split()))
arr = []
min_len = 1000000001
for i in range(0, n):
temp = int(input())
arr.append(temp)
arr.sort()
print(solve(c))3. 풀이 메모
Brute Force로 해결하려고 하면 O(N^2)의 시간 복잡도로 시간 초과가 발생한다. 집을 고르는 모든 조합에서 대해서 고려하기보다는 더 괜찮은 접근법이 필요하다.
여기서는 이분 탐색을 활용한다. 다만 실제 문제 풀이를 할 때는 이분 탐색을 적용해도 되는지 긴가민가한 부분이 있어 다른 풀이를 고민하다 해답을 보고 문제를 해결했는데, 이 글에서는 그 '긴가민가했던 부분' 을 집중적으로 고찰해보려고 한다.
1) 루프에서 항상 첫번째 집을 포함시켜 카운트 해도 되는가?
된다. 모든 최적의 경우는 반드시 가장 처음 집이나 가장 마지막 집을 포함시켜야만 한다. 이러한 논리가 성립하는 이유를 예시를 들어가면서 설명하면 다음과 같다.
1. 6개의 집 중에서 2개의 집을 선택하는 경우
양 끄트머리에 있는 두 개의 집을 선택하면 가장 인접한 두 집간의 거리가 최대가 된다.
2. 6개의 집 중에서 3개의 집을 선택하는 경우
반드시 구석의 집 하나를 선택 해야 한다. 그 이유를 알아보기 위해 이렇게 생각해보자:
'' 4개의 집 중에서 3개의 집을 선택하자. 그런데 갑자기 문제 조건이 바뀌어서 4개의 집 양 옆에 추가로 집이 생겨서 총 6개가 되었다고 치자. 그렇다면 기존의 선택한 3개의 집은 더이상 인접한 집간의 거리가 최대가 되는 선택지가 아닐 수도 있다. 기존 선택한 3개의 집에서 양 옆의 선택집을 한칸 옆으로 늘린다면, 최대 인접 거리는 갱신될 수 있기 때문이다.''
다시 말해, 6개의 집이 있더라도 중앙 4개만 선택하는 경우가 인접한 집간의 거리가 최대가 되는 경우는 없다는 뜻이다. 반드시 구석의 집 하나 혹은 둘을 선택해야 한다. 설령 좌우로 새로 생긴 집의 거리가 좁아서 최대 인접 거리가 갱신되지 않더라도, 문제를 해결하는데는 지장이 되지 않는다.
따라서, 첫번째 집을 포함시켜서 카운트를 하는 접근은 항상 최적의 해를 내놓는다.
2) left_val = 1로 설정해도 되는가?
된다. 이분 탐색의 원리를 생각한다면, 가능한 최저값부터 고려하더라도 정답에 근접하도록 접근할 수 있다. 사실, 1부터 고려하는게 모든 케이스를 고려하기 위한 가장 안전한 방법 중 하나이기도 하다. 만약 영 불편하다면 미리 각 집간의 인접 거리를 계산하고, 그 최소값을 left_val로 설정해도 되지만, 불필요한 연산 낭비이다.
4. 코멘트
문제를 이해하는데 다소 애를 먹었었다. 거리의 최대값을 구하는 것은 맞지만, '가장 인접한' 이라는 조건이 붙는 이상 결국 한번 뽑은 집들의 집합 간의 거리에서 최소값을 구해야 한다. 위와 같은 조건을 이해한다면, 복잡하게 모든 집의 조합에 대해서 각 거리에 대한 최소값을 계산할 필요 없이 그냥 '최소로 추정되는 값' 을 미리 정해놓고 거리를 연산하고, 조건을 만족하지 못할 시에는 이 추정치를 조정하는 방식으로 문제를 해결할 수 있다.
