. 아~ 와이파이 잘되는 집을 찾으시는구나? (백준 2110 : 공유기 설치)
본문 바로가기
프로그래밍 공부/백뚠

아~ 와이파이 잘되는 집을 찾으시는구나? (백준 2110 : 공유기 설치)

by 불냥이_ 2020. 12. 18.

2110번: 공유기 설치 (acmicpc.net)

 

2110번: 공유기 설치

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가

www.acmicpc.net

 

N : 집 갯수, C : 공유기 갯수

 

우선, 집 좌표를 받아서 sort하자 

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

딱봐도 맨 처음과 맨 끝 좌표에는 좌표기를 설치해야될 것 같지 않는가. (반례가 있나? 없다고 생각하지만) 

 

뭔가 완전 탐색을 해야될 것 같지만, 이분탐색 문제이므로 이분탐색으로 풀어보자.

그러면, 답(가장 인접한 거리)을 기준으로 생각하는 것이 편할 것이다.

가장 인접한 거리가 x일 때, 공유기 C를 설치할 수 있는가? 

 

간격(distance)은 첫집(low : house[0])과 마지막 집(high:[len(house)-1]) 의 중간거리가 될 것이다.

그리고 이 간격 이상으로 공유기를 설치할 때, 공유기를 다 설치할 수 있는지를 판별한다. (def judge)

만약 설치할 수 있다면(return 1), low를 distance + 1로 하고, (거리를 더 벌리고) 아니라면 high를 distance - 1로 한다. (거리를 좁힌다.)

 

def find(C): # house는 집 좌표, C는 공유기 갯수
    low = house[0]
    high = house[len(house)-1]
    
    
    while True:
        distance = (high + low) // 2
        if judge(distance, C) == True:
            if low >= high:
                break
            low = distance + 1

        else:
            high = distance - 1

    return distance

judge는 맨 왼쪽부터 시작하여, 공유기를 심은 집과 다음 집간 거리가 distance 이상이라면 공유기를 심는다.

 

공유기 집 (share : 첫 시작은 house[0]이 된다.) 과 다음 공유기 집(house[i]) 간의 거리 (house[i] - share)가 distance 이상이라면 C (공유기 갯수)를 줄이고, 아니라면 다음 집으로 넘어간다. 

 

그리고 귀결 조건은 C가 0이 되면 성공 (True 반환). i가 len(house)-1 이 되었는데, C가 남아있으면 False 반환한다.

def judge(distance, C):
    remain = C - 1
    share = house[0]
    for i in range(len(house)):
        if house[i] - share >= distance:
            remain -= 1
            share = house[i]
        if remain == 0:
            break
    if remain >= 1:
        return False
    else:
        return True

 

전체 함수는 다음과 같다.

import sys


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


def find(C): # house는 집 좌표, C는 공유기 갯수
    low = house[0]
    high = house[len(house)-1]
    
    
    while True:
        distance = (high + low) // 2
        if judge(distance, C) == True:
            if low >= high:
                break
            low = distance + 1

        else:
            high = distance - 1

    return distance


def judge(distance, C):
    remain = C - 1
    share = house[0]
    for i in range(len(house)):
        if house[i] - share >= distance:
            remain -= 1
            share = house[i]
        if remain == 0:
            break
    if remain >= 1:
        return False
    else:
        return True

print(find(C))

제출한 결과, 파이썬과 파이파이 둘 다 70% 정도에서 시간 초과가 떴다.

로직은 맞으나, 뭔가 비효울적이라는 말이 된다.

어떻게 수정해야할까?

 

 

놀랍게도 범인은 초기값과 마지막 값에 있었다.

생각해보자. 거리의 최솟값은 0 이지, house[0]이 아니다. 만약 house[0]가 엄청나게 높은수이면, 시작점도 실제 중간거리보다 훨씬 어긋날뿐더러 그 거리에 대해서는 모두 공유기 설치가 성공하기 때문에 공유기 설치 판정에서도 시간이 많이 잡아먹히게 된다.

 

또한, high 역시 house[N-1]이 아니라, house[N-1] - house[0]이 된다. 최대거리는 첫집과 마지막 집 사이의 거리가 되기 때문이다.

 

이진 탐색에서 초기값에 대해서도 신경써야 한다는 것을 알려준 문제였다.

 

 

 

 

 

 

댓글