백준 2110 공유기 설치 문제풀이

문제 

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

2110번: 공유기 설치

 

 

문제 접근 방식

문제를 잘못 이해하고 풀다가 꼬여버린 문제.

초기에 공유기의 반경을 설정하고 그 반경을 이분법으로 조절해가면서 푸는 방법으로 접근했으나 중간에 뭔가 잘못되고 있다는 것을 느꼈음.. 문제를 잘못 이해했다는 것을 알았으나 이미 생각이 꼬여서 다른 풀이 참고함.

 

 

decision(d) = 주어진 집 N개 중 c개를 선택해서 공유기를 놓을 때, 각 공유기의 거리가 d 이상인가?

로 변환한다. 

특정 d 에 대해 decision 함수가 true를 반환한다면 d를 증가시켜서 가능한지를 살펴보고, false라면 감소시키면서 최대 d 값을 구한다.

 

구체적인 decision 함수는 그리디로 구현되어 있다.

decision(d) = 가장 첫번째 집에서 부터 공유기를 설치하고, d 이상인 거리의 집이 나올 때 마다 공유기를 설치한다.

 

그렇게 공유기를 설치하다가 c개를 모두 설치하면 true를 반환하고, c개를 설치 못했다면 false를 반환한다.

 

이렇게 코드를 구현할 때, 의문이 생긴다.

1. d 이상의 거리의 집이 나오면 바로 공유기를 설치하는데, 중간에 C개가 되면 종료되어도 괜찮은가?

2. 공유기를 중간 지점부터 설치할 수도 있는건데, 첫번째에 설치해도 괜찮은건가?

 

 

1. 중간에 c개를 다 설치해도 괜찮은가?

아래 그림처럼 중간에서 c개를 설치하고 decision 함수가 true를 반환했다고 가정하자.

 

이때 마지막에 설치된 공유기를 끝에 있는 집으로 옮기면 c-1번째 공유기와 c번째 공유기의 거리는 4+a 가 되며, 이는 d 이상이므로 모든 공유기 사이의 거리가 d 이상을 그대로 만족한다. 즉, decision 함수에 영향을 미치지 않기 때문에 둘의 결과는 같다. 그러므로 d 이상의 공유기를 바로 설치해도 괜찮다.

 

 

2. 공유기를 중간 지점부터 설치할 수도 있는건데, 첫번째에 설치해도 괜찮은건가?

아래 그림처럼 중간에서부터 공유기를 설치하여 모든 공유기의 거리가 d= 2 이상이라고 가정하자.

 

이때, 공유기의 시작위치를 첫번째로 옮긴다고 하면 첫번째 공유기와 두번째 공유기 사이의 거리는 5+a 가 되며, 이는 d 이상을 똑같이 만족한다. 즉, 모든 공유기 사이의 거리가 d 이상을 만족하기 때문에 두 경우의 결과값이 항상 같다는 것을 알 수 있다. 

그렇기 때문에 첫번째 집에 공유기를 설치해도 상관이 없는 것이다.

 

1,2 을 통해 decision 함수를 그리디로 구현할 수 있다.

 

시간 복잡도

이분 탐색의 시간 복잡도가 O(d) 이고, 그리디 함수의 시간복잡도가 O(n) 이다. 각각의 d,n의 최대값이 1e9, 2e5 이므로 시간내에 동작함을 알 수 있다.

 

코드

import sys

input=sys.stdin.readline
MAX=int(1e9)

# decision(d) = 노드의 간격을 d 이상으로 하여 공유기 c 대를 설치할 수 있는가?
def decision(d):

    # 첫번째에 공유기를 설치해도 return 값에 영향을 미치지 않는다.
    index=0
    count=1
    for i in range(1,n):
        if houses[i]-houses[index]>=d:
            index=i
            count+=1
        if count ==c:
            return True

    return False

if __name__=='__main__':
    global houses,n,c
    n,c=map(int,input().split())
    houses=sorted([int(input()) for _ in range(n)])

    s,e=0,MAX
    answer=0
    while s<=e:
        mid=(s+e)//2
        if decision(mid):
            answer=mid
            s=mid+1
        else:
            e=mid-1

    print(answer)

 

회고

그리디에 대한 이해도 부족과 문제를 잘못 이해하고 접근한 것이 섞여서 완전 꼬여버렸다.

입출력 예시만 제대로 분석하고 풀었어도 잘못 이해하는 일은 없었을 것 같은데..반성하자