BOJ_2110 공유기 설치

• TOC {:toc}

이 글은 백준 온라인 저지의 2110번 문제를 파이썬(Python)으로 풀이한 것을 모아놓은 글입니다.

일종의 연습 기록이며 제가 정답을 받은 코드와 참고할만한 다른 코드를 같이 기록합니다. 필요한 경우 코드에 대한 해설을 기록합니다만 코드는 통과했어도 해설은 틀릴 수 있기 때문에 가볍게 참고해주시길 부탁드립니다. 피드백은 편하신 방법으로 자유롭게 주시면 감사하겠습니다.

2021.05.27 (Python)

풀이 없음

피드백

• 아예 작성을 시작조차 못했다. 처음인 듯.
• C를 기준으로 거리를 계산하는 것이 아니라 반대로 임의의 거리를 기준으로 C를 계산하는 것에서부터 출발했어야 했다.

2022.03.23 (JS)

const fs = require("fs");
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");

const [N, C] = input
    .shift()
    .split(" ")
    .map((n) => parseInt(n));
const P = input.map((n) => parseInt(n)).sort((a, b) => a - b);
let res = 0;

function allRouterUsed(mid) {
    let count = 1;
    let prev = P[0];
    for (const pos of P) {
        if (pos - prev >= mid) {
            prev = pos;
            count += 1;
        }
    }
    return count >= C ? true : false;
}

let min = 1;
let max = P[P.length - 1] - P[0];

while (min <= max) {
    mid = parseInt((min + max) / 2);

    if (allRouterUsed(mid)) {
        res = mid;
        min = mid + 1;
    } else {
        max = mid - 1;
    }
}

console.log(res);

디버깅

• 첫 번째 실행했을 때 시간초과 나왔는데, 이분 탐색을 반복으로 한 게 아니라 재귀로 돌려서 그런 것 같다.
• 처음 인풋 받을 때 trim 안했더니 4번이나 틀렸다.

피드백

• 이전에 풀었던 기억이 나서 접근 자체는 금방할 수 있었는데 아직도 이런식으로 사고를 하는 것 자체가 익숙하지 않은 것 같다.

참고 답안

# 풀이 1-1
import sys
input = sys.stdin.readline

N, C = list(map(int, input().split()))
H = sorted([int(input()) for _ in range(N)])

# start를 1로 둔다.
start = 1
# end를 처음과 마지막 집 사이의 거리로 지정한다.
end = H[-1] - H[0]
res = 0

while start <= end:
    mid = (start + end) // 2

    count = 1
    value = H[0]
    # H 안의 값 x에 대해서
    for x in H:
        # 해당 값이 현재 값에서 mid를 더한 것보다 크면
        if x >= value + mid:
            # value를 현재 값으로 바꾸고
            value = x
            # count를 증가시킨다
            count += 1
    # count가 공유기 개수보다 많으면
    if count >= C:
        # start를 mid 다음 값으로 바꾸고
        start = mid + 1
        # 결괏값을 mid로 바꾼다
        res = mid
    # 적으면
    else:
        # end를 mid 이전 값으로 바꾼다. 
        end = mid - 1

print(res)

# 풀이 1-2
from sys import stdin

N, C = list(map(int, input().split()))
H = sorted([int(input()) for _ in range(N)])

def count(gap):
    count, val = 1, H[0] + gap
    for x in H:
        if x >= val:
            count += 1
            val = x + gap
    return count

start, end = 1, (H[-1] - H[0]) // (C - 1) + 1

while start + 1 < end:
    mid = (start + end) // 2
    start, end = (mid, end) if count(mid) >= C else (start, mid)
print(start)

아이디어 & 풀이

이진 탐색(binary search)을 이용하는 문제이다.

• 일반적인 이진 탐색은 수열 안에서 주어진 값과 동일한 값을 찾는 알고리즘이다.
• 이 문제에서는 찾아야 하는 특정 값이 주어지는 것은 아니기 때문에 이진 탐색을 응용해야 한다.

문제에서 구하려고 하는 것은 C개의 공유기를 N개의 집에 설치했을 때 ‘가장 가까운’ 공유기 사이의 거리의 최댓값이다.

• 공유기 사이의 거리 중 ‘가장 가까운’ 값은 현재 공유기 사이의 여러 거리 값 중 최솟값이다.
• 공유기 사이의 거리를 이 값(gap)에 최대한 가깝게 배열하면 당연히 N개의 집 안에 모두 들어가야 한다.
  • 바로 인접한 공유기 사이의 간격이 최솟값보다 큰 경우도 있기 때문에 최대한 가깝게 배열하는 것이다.
• C개의 공유기가 N개 안에 들어가지 ‘않게’ 되는 간격의 직전 값이 가장 가까운 공유기 사이의 거리의 ‘최댓값’이 된다.

결과적으로 임의의 간격을 정해가면서 그 간격으로 공유기를 배열했을 때 집 안에 모두 들어가는지 판단하면 된다.

그러면 공유기 찾기에 다음과 같이 이진 탐색을 적용할 수 있다.

풀이 과정은 다음과 같다.

공유기 사이의 거리의 시작 값(start)과 끝값(end) 정한 뒤 그 중간값을 구한다.

• 첫 값은 각각 공유기 사이의 거리의 최솟값과 최댓값이다.
• end 초깃값을 처음과 마지막 공유기 사이의 거리가 아니라 그걸 C - 1로 나눈 뒤 1을 더한 값으로 지정해도 된다.
  • 공유기가 C개 있을 때 공유기 사이의 거리의 최솟값은 총 거리를 C - 1등분한 것 보다 클 수 없다.
    • 공유기가 C개고, 그럼 거리를 C - 1등분 하므로 C가 아니라 C - 1로 나눈다.
  • 총 거리가 C - 1로 나누어떨어지지 않으면 소수점이 버림되기 때문에 1을 더해준다.

일반적인 이진 탐색에서는 중간값과 기준값을 바로 비교하지만, 이 문제는 주어진 거릿값(중간값)으로 공유기를 배열했을 때 들어갈 수 있는 공유기의 개수 (i.e., count)를 계산하는 과정이 필요하다.

• 주어진 좌표를 순회하면서 현재 값이 이전 값보다 주어진 거리 이상으로 크면 count를 늘리고 기준을 현재 값으로 바꾼다.

count를 기준인 C와 비교한다.

• count가 C보다 크면 거릿값을 늘려도 되므로 start를 중간값 + 1로 키운다.
• count가 C보다 작으면 더 많은 공유기가 들어가야 하므로 end를 중간값 - 1로 줄여 거릿값을 줄인다.

위 과정을 반복한다.

• 재귀를 사용할 수도 있다.