[2110] 공유기 설치(python)

1. 문제

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

2110번: 공유기 설치

2. 구현 과정

- 읽을 수록 헷갈려서 문제를 이해하는데 오래걸렸다. 인접한 공유기의 최대거리? 가 어떤 의미인지를 빨리 이해하는 게 중요한 것 같다.

 

- 맨 처음 완전 탐색으로 전체 N개 중 C개를 조합으로 구한 후, 가장 먼 거리를 구하려 했는데, 시간 초과가 난다.

 -> 파이썬 기준 2초 : 약 4000만 연산. nC2만 해도 20만*10만 = 200억으로 시간 초과 발생

 

- 인접한 공유기 간의 거리 중 최대 거리를 구해야 함 => 해당 거리를 dis라고 정의하면, dis의 최소값은 가장 가까운 두 집 사이 거리, 최대값은 가장 오른쪽에 있는 집 좌표 - 가장 왼쪽에 있는 집 좌표(공유기가 1개 설치되어 있을 경우 가장 첫번째 집 혹은 가장 오른쪽 집에 설치했을 때 ) 이다.

=> 거리의 최소값과 최대값이 정해졌으므로 이분 탐색으로 구현할 수 있겠다!

=> 이분 탐색은 배열 값이 정렬되어야 하므로, 집의 좌표 받을 때 정렬된 List로 만들어야 겠다. ( 자료구조 확정 )

=>  인접한 공유기 간의 거리(mid) = (최소값 + 최대값 ) // 2 로 한 후, 설치할 수 있는 공유기의 개수를 구한다. 

=> 설치한 공유기 개수 < C 이면 공유기 간의 거리가 너무 먼 것이므로, 최대값을 mid + 1로 줄인다. 반대로 설치한 공유기 개수 > C 이면 정답으로 가능한 수가 된다. 정답으로 가능한 거리들 중 가장 긴 값을 출력한다.

 

- 유의 사항1 : 공유기의 개수를 구할 때, 무조건 (이전에 설치한 좌표) + mid 의 좌표에 공유기를 설치할 수는 없다. ( 집에서만 공유기를 설치할 수 있는데, 해당 좌표값에 집이 있음을 보장할 수 없으므로)

 

- 유의 사항2 : 공유기의 개수를 구할 때, 무조건 첫번째 집에는 공유기를 설치해야 한다.

      ex1) 가장 인접한 공유기가  (첫번째 공유기 - 두번째 공유기) 간 거리이면서, 첫번째 공유기는 왼쪽에서 두번째 이상의 집에서 설치되었을 경우 :  1,2,4,8,9가 있을 때 (2,4,9)에 공유기를 설치하면 2-4간 거리가 가장 인접한 거리이다. 이 경우, 1,4로 설치했을 때가 더 긴 거리이므로 가장 긴 거리가 될 수 없다.

      ex2) 가장 인접한 공유기가 (i 번째 공유기 - i + 1번째 공유기, i >=2)간 거리이면서, 첫번째 공유기는 왼쪽에서 두번째 이상의 집에서 설치되었을 경우: 1,2,4,8,9가 있을 때 (4,8,9)에 공유기를 설치하면 8-9가 인접한 거리이다. 이 경우, 4->1에 공유기를 설치해도 어차피 가장 인접한 거리는 8-9인 1이므로 정답에 영향을 주지 않는다.

   => 따라서 가장 첫번째 집에 공유기를 설치하는 경우가 항상 인접한 거리가 긴 경우이다.

3. 실수한 것 & 새로 알게된 것

1) 파이썬의 set은 자동정렬이 안된다!!!

2) 2차원 배열의 최대값 구하기 : max( map (max, array) )

3) 입력값들을 정렬해서 list에 넣고 싶을 때 :  array = sorted( list (int(input()) for _ in range(N)) )

4) 이분탐색 할 때..꼭... int ( min + max // 2) 로 형 변환 하자!!!1

5) 배열의 시작 값 : array[0], 마지막 값 : array[-1]

 

4. 코드

#입력 받기
N, C = map(int,input().split())
answer = 0
houses = sorted(list(int(input()) for _ in range(N)))

min_distance = 1
max_distance = houses[-1]  

#이분 탐색을 통해 가장 짧은 거리를 mid_distance로 했을 때, 공유기 설치가 가능한지 확인
while min_distance <= max_distance:
	mid_distance = int((min_distance + max_distance) // 2) #인접한 공유기 간의 최소 거리 
	installable_router = C - 1 #설치 가능한 공유기개수
	before_house = houses[0] #직전에 공유기를 설치했던 집 번호 

#1번 집부터 공유기를 설치하고,최소 mid_distance 거리만큼 공유기를 설치했을 때 설치 가능한 공유기 개수
	for i in range(1, len(houses)):
		if houses[i] - before_house >= mid_distance:
			before_house = houses[i]
			installable_router -= 1
	
	if installable_router > 0:
		max_distance = mid_distance - 1

	else:
		min_distance = mid_distance + 1
		answer = max(answer,mid_distance)

print(answer)