[백준] 2110번 : 공유기 설치 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

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

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 집에 정해진 개수만큼 공유기를 설치할 때 가장 인접한 두 공유기 사이의 최대 거리를 구하는 문제이다.

가장 인접한 두 공유기 사이의 최대 거리를 구하려면 공유기가 설치된 집의 위치를 알아야 한다.

공유기를 설치할 때 그 거리의 최소 거리인 1과 최대 거리인 가장 양끝에 위치한 두 집의 거리를 시작으로 하여 공유기를 설치하면서 최소 거리와 최대 거리를 계속적으로 수정해 나간다.

공유기를 설치할 때는 최소 거리와 최대 거리를 통해 그 중간 거리를 구하고 공유기가 설치된 바로 이전 집에서 중간 거리보다 같거나 더 멀리에 있는 집에 공유기를 설치한다.

이후 공유기가 설치된 집의 수가 공유기의 수보다 적으면 더 좁은 간격으로 공유기를 설치해야 하므로 최대 거리를 중간 거리 이전으로 수정한다.

반면 공유기가 설치된 집의 수가 공유기의 수보다 많거나 같으면 더 넓은 간격으로 공유기를 설치해야 하므로 최소 거리를 중간 거리 다음으로 수정한다.

그리고 해당 경우에는 중간 거리가 두 공유기 사이의 최대 거리일 수 있으므로 해당 중간 거리를 결과에 저장한다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 입력받는다. import sys
2. 집의 개수와 공유기의 개수를 입력받는다. N, C = map(int, sys.stdin.readline().split())
3. 집의 위치를 저장할 리스트를 생성하고 house = []
   
4. 집의 개수만큼 반복하며 집의 위치를 입력받아 리스트에 추가한다. for _ in range(N): house.append(int(sys.stdin.readline()))
5. 집의 위치를 오름차순으로 정렬한다. house.sort()
6. 공유기 사이의 최소 거리를 저장할 변수를 생성하고 1을 저장한다. MIN = 1
7. 공유기 사이의 최대 거리를 저장할 변수를 생성하고 양끝 집의 거리를 저장한다. MAX = house[-1] - house[0]
8. 최소 거리가 최대 거리보다 크지 않으면 반복한다. while (MIN <= MAX)
   1. 최소 거리와 최대 거리를 기준으로 중간 거리를 구한다. mid = (MIN + MAX) // 2
   2. 처음 집의 위치를 현재 집의 위치로 저장한다. now = house[0]
   3. 공유기를 설치한 개수를 저장할 변수를 생성하고 처음 집에 공유기를 설치해 1을 저장한다. count = 1
   4. 그다음 집부터 차례대로 집의 위치를 가져오며 for h in house[1 : ]
      1. 만약 가져온 집의 위치에서 중간 거리를 뺀 값이 현재 집의 위치보다 크거나 같으면 if (h - mid >= now)
         1. 해당 집에 공유기를 하나 더 설치하고 count += 1
         2. 가져온 집의 위치를 현재 집의 위치로 저장한다. now = h
   5. 모든 집을 가져와 비교한 후 설치한 공유기의 개수가 설치하려는 공유기의 개수보다 작으면 최대 거리를 중간 거리 이전으로 수정한다. if (count < C): MAX = mid - 1
   6. 반면에 설치한 공유기의 개수가 설치하려는 공유기의 개수보다 크거나 같으면 else
      1. 최소 거리를 중간 거리 다음으로 수정하고 MIN = mid + 1
      2. 결과 변수를 생성하여 중간 거리를 결과 변수에 저장한다. result = mid
9. 전체 반복이 종료된 후 결과 변수에 저장된 값이 두 공유기 사이의 최대 거리가 된다. print(result)

3. 소스코드

import sys

N, C = map(int, sys.stdin.readline().split())
house = []
for _ in range(N):
    house.append(int(sys.stdin.readline()))

house.sort()

MIN = 1
MAX = house[-1] - house[0]
while (MIN <= MAX):
    mid = (MIN + MAX) // 2
    now = house[0]

    count = 1
    for h in house[1 : ]:
        if (h - mid >= now):
            count += 1
            now = h

    if (count < C):
        MAX = mid - 1
    else:
        MIN = mid + 1
        result = mid

print(result)