[백준 - Python] 2110 - 공유기 설치

0.  문제 링크

 

 

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

2110번: 공유기 설치

---

1.  풀이 방법

 

 

내 기준 가장 신박했던 문제

 

문제 유형은 이분 탐색 + 매개 변수 탐색이다.

이 유형은 최적화 문제를 결정 문제로 바꿔서 푸는 문제이다.

그렇다면 어떤 부분이 최적화일까? 를 먼저 생각해야 하는데, 문제에 나와있듯이 가장 인접한 두 공유기 사이의 '최대 거리'이다.

그러면 이 부분을 결정 문제로 바꿔야 하는데, 어떻게 결정 문제로 바꿔야 하는지 잘 몰라서 결국 구글링을 해버렸다.

 

결론적으로 최대 거리를 결정 문제로 바꾸면 되는 문제

따라서 아래의 시퀀스를 따라가면 정답을 얻을 수 있다.

• 최대 거리가 1일 때 -> 공유기가 c개 이상 가능? -> 가능하면 최대 거리는 1
• 최대 거리가 2일 때 -> 공유기가 c개 이상 가능? -> 가능하면 최대 거리는 1에서 2로 수정
• 최대 거리가 3일 때 -> 공유기가 c개 이상 가능? -> 가능하면 최대 거리는 2에서 3으로 수정
• 최대 거리가 4일 때 -> 공유기가 c개 이상 가능? -> 불가능, 최대 거리는 3개다.
  • 그렇다면 최대 거리는 3이 된다.

 

이런 식으로 최적화 문제를 바꿔버리는 게 매개 변수 탐색이다.

여기서 이제 이분 탐색이 쓰이는 것이다.

1에서 시작하는 linear한 증가로 찾는 것이 아닌, 이분 탐색으로 찾으면 훨씬 빠르기 때문이다.

 

1. 최소 거리는 1, 최대 거리는 양 끝의 집 사이의 거리
2. 이분 탐색으로 최소 거리와 최대 거리의 mid를 거리라고 하고, 해당 mid 거리만큼 공유기를 설치했을 때, c개 이상 설치할 수 있는가?
   1. 참고로 공유기는 무조건 mid 이상의 거리를 가져야 한다.

 

간단하다.

최근 코테에서 자주 나오는 유형이라고 하니, 자주 풀어보면 좋을 것 같다.

---

2.  코드

 

 

import sys
input = sys.stdin.readline


if __name__ == "__main__":
    n, c = map(int, input().split())
    maps = []
    for _ in range(n):
        maps.append(int(input()))

    maps.sort()

    start, end = 1, maps[-1] - maps[0]      # 최소 거리와 최대 거리
    ans = 0

    if c == 2:
        print(end)
    elif c == n:
        print(min([maps[i + 1] - maps[i] for i in range(n - 1)]))
    else:
        while start < end:
            mid = (start + end) // 2        # mid 거리 이상만큼 공유기를 설치함

            cnt = 1
            bef = maps[0]

            for i in range(n):
                if maps[i] - bef >= mid:
                    cnt += 1
                    bef = maps[i]

            ## 아래 주석까지의 부분이 잘 이해가 안 감
            if cnt >= c:
                ans = mid
                start = mid + 1
            elif cnt < c:
                end = mid
            ##

        print(ans)

---

3.  마무리