BOJ_2212 센서

• TOC {:toc}

이 글은 백준 온라인 저지의 2212번 문제를 풀이한 것을 모아놓은 글입니다.

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

2021.07.13 (Python)

import sys

int(input())
K = int(input())

sensors = list(set(map(int, input().split())))
sensors.sort()
N = len(sensors)

if K >= N:
    print(0)
    sys.exit()

dist = [sensors[i + 1] - sensors[i] for i in range(len(sensors) - 1)] 
dist.sort()
for _ in range(K - 1):
    dist.pop()

print(sum(dist))

아이디어 & 풀이

이 문제의 목적은 수직 선상에 놓인 센서를 그 거리의 합이 최소가 되도록 K개의 묶음으로 나누는 것으로 볼 수 있다.

센서 묶음은

• 동일한 집중국을 공유하는 센서들의 집합으로
• 묶음의 크기(첫 센서와 마지막 센서 사이의 거리)가 집중국이 수신해야 하는 영역이 된다.
  • 묶음의 어느 위치에 집중국을 두던, 같은 크기의 수신 영역을 갖는다.
• 이는 묶음 내의 인접한 센서 사이의 거리의 합으로 볼 수 있다.

K개의 묶음으로 나누기 위해서는

• 모든 인접한 센서를 연결한 뒤 K - 1개의 연결을 끊으면 된다.
• 센서 사이가 끊어졌다는 것은 한 묶음 내의 수신기가 다른 묶음의 센서를 수신하지 않아도 된다는 것과 같다.

수신기의 수신 영역을 최소로 하기 위해서는

• 두 센서사이의 거리가 최대인 연결부터 끊으면 되므로
• 그리디 알고리즘을 이용하면 된다.
  • 모든 인접한 센서 사이의 거리를 구해 정렬한 뒤,
  • 그 값이 큰 것부터 K - 1개 제거한다.

디버그

• 집중국의 수가 센서의 수보다 많은 경우를 고려해주어야 한다.
  • 이 경우 수신 가능 영역의 합은 0이 되므로 0을 출력하고 실행을 종료한다.

피드백

• 문제 이해를 잘못했다.
  • 집중국을 세우면 ‘모든 센서에 대해서’ 해당 집중국과 센서 사이의 거리 차를 구해 더해야 하는 줄 알았는데
  • 그냥 현재 집중국에서 수신해야 하는 가장 먼 센서까지의 거리만 구하면 되는 것이었다.
• 문제를 풀다 보면 문제에서 중점적으로 계산해야 하는 포인트가 문제의 핵심 대상과 다른 경우가 많은데 그걸 인지하고 있으면서도 포인트를 잡는 게 어렵다.
  • 이번 문제에서 핵심 대상은 집중국이라 집중국을 움직이면서 센서 묶음을 ‘만들어가는’ 방향으로 문제를 풀었었는데,
  • 거기에 그리디 알고리즘을 쓰는 방법이 갈피가 안 잡혔다.
  • 실제로 포인트로 잡아야 하는 대상은 ‘인접한 센서 사이의 거리’였고 이를 일단 전부 만든 뒤 ‘제거해 가는데’ 그리디 알고리즘을 적용했어야 했다.
  • 집중국을 놓아서’가 아니라 ‘연결을 제거해서’ 센서의 묶음을 만들어 간다는 발상으로 전환하는 게 그렇게 해야 한다는 인지는 하고 있으면서 적용이 쉽지 않은 것 같다. 앞으로 집중해서 연습해봐야겠다.

2022.04.06 (JS)

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

function main() {
    if (N === 1) return 0;

    const gap = Array(N - 1).fill(0);
    let gapSum = 0;

    for (let i = 0; i < N - 1; i += 1) {
        gap[i] = sensors[i + 1] - sensors[i];
    }
    const selectedGap = gap.sort((a, b) => b - a).slice(0, K - 1);
    if (selectedGap.length) {
        gapSum = selectedGap.reduce((prev, curr) => prev + curr);
    }

    return sensors[sensors.length - 1] - sensors[0] - gapSum;
}

const N = parseInt(input[0]);
const K = parseInt(input[1]);
const sensors = input[2]
    .split(" ")
    .map((n) => parseInt(n))
    .sort((a, b) => a - b);

console.log(main());

디버그

• K가 1인 경우를 제대로 처리해주지 않아서 틀렸다. K가 1이면 slice의 결과가 빈 배열이라서 reduce를 할 때 문제가 발생하는 것 같다.

피드백

• 이전에 푼 기억에 의존해서 푸는 기분이다.

참고 답안

# 동일한 풀이를 간결하게 작성

N = int(input())
K = int(input())

sensors = sorted(set([*map(int, input().split())]))
dist = sorted([sensors[i] - sensors[i - 1] for i in range(1, len(sensors))], reverse=True)

print(sum(dist[K - 1:]))