사용자 도구

사이트 도구


ps:problems:boj:2110

공유기 설치

ps
링크https://www.acmicpc.net/problem/2110
출처BOJ
문제 번호2110
문제명공유기 배치
레벨실버 1
분류

파라메트릭 서치

시간복잡도O(n(logx + logn))
인풋사이즈n<=200,000, x<=10^9
사용한 언어Python
제출기록38092KB / 396ms
최고기록140ms
해결날짜2021/06/04

풀이

  • 파라메트릭 서치로 푸는 문제.
  • C개로 X 이상의 거리를 유지할수 있다.
  • X를 입력으로 받아서, C개의 공유기를 사용해서 공유기 사이의 거리가 전부 X 이상인 배치가 가능한지를 확인하는 함수를 만들면 된다. 이 함수가 true를 리턴하는 X의 최댓값을 이진 탐색으로 찾는다.
  • C개의 공유기로 이러한 배치가 가능한지를 확인하는 것은, 그리디한 방법을 적용한다. C개보다 많은 공유기로 간격 유지가 가능하다면, 거기서 공유기를 빼더라도 최소 간격이 좁아지지는 않으니까 뺄수록 C개로도 거리 유지가 가능하다. 따라서 최소 간격을 유지하는 선에서 공유기를 최대한 많이 배치하도록 시도해보고, 그 갯수가 C개 이상이 되면, C개로 배치가 가능하다고 판단할 수 있다. 좌표를 왼쪽에서부터 훑으면서 이전 공유기의 위치와의 간격이 최소간격 이상이 될때마다 공유기를 배치하는 식으로 하면 된다.
  • 먼저 집의 좌표를 정렬해야 하기 때문에 O(NlogN)이 필요하다. 좌표를 정렬시키고 나면, 배치가 가능한지 확인하는 함수는 O(N)에 동작하고, 정답의 후보를 0~X (X=최대 좌표) 에서 이진 검색으로 찾아야 하므로, 저 함수를 O(logX)번 호출해야 한다, 따라서 총 시간복잡도는 O(NlogN + NlogX)
  • teflib.algorithm.binary_search 함수는 범위내의 최댓값이 아닌 최솟값만 찾아주도록 구현되어 있기 때문에 살짝 바꿔쓸 필요가 있다. 함수를 배치가 불가능한지를 확인하도록 바꿔 만들어서, 배치가 불가능한 최솟값 X를 찾도록 해야 한다. 이렇게 하면 X-1이 배치가 가능한 최댓값이 된다.

코드

"""Solution code for "BOJ 2110. 공유기 설치".

- Problem link: https://www.acmicpc.net/problem/2110
- Solution link: http://www.teferi.net/ps/problems/boj/2110
"""

import sys
from teflib import algorithm


def main():
    def is_impossible(dist):
        count = 1
        prev = x[0]
        for p in x[1:]:
            if p - prev < dist:
                continue
            prev = p
            count += 1
            if count >= C:
                return False
        return True

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

    x.sort()

    print(algorithm.binary_search(0, x[-1], is_impossible) - 1)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
A F​ J K Y
 
ps/problems/boj/2110.txt · 마지막으로 수정됨: 2021/06/04 16:34 저자 teferi