백준 2212번 - 센서 (JavaScript)

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

2212번: 센서

생각해보기

센서 N개를 K개의 분류로 나눠야 한다. 이를 위해서 K-1개의 기준선이 필요하다.

 

기준선은 센서 사이의 간격이 큰 것부터 선정한다. 이렇게 되면 선정된 기준선의 간격은 무시할 수 있게 되고 수신 가능 영역의 합이 최소가 된다.

 

센서 사이의 간격을 나타내는 배열을 diff라고 했을 때, 기준선으로 선정된 간격은 무시할 수 있으므로 지울 수 있다. 따라서 diff 배열을 내림차순으로 정렬한 후, K-1개의 원소를 지우고 나머지 원소들의 합을 구하면 된다.

 

 

풀이)

const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const solution = (N, K, data) => {
  if (N <= K) {
    return 0;
  }

  data.sort((a, b) => a - b);

  let answer = 0;
  const diff = [];

  for (let i = 0; i < data.length - 1; i++) {
    diff[i] = data[i + 1] - data[i];
  }
  diff.sort((a, b) => b - a);

  for (let i = K - 1; i < diff.length; i++) {
    answer += diff[i];
  }

  return answer;
};

let N = null;
let K = null;
let data;
let count = 0;

rl.on("line", function (line) {
  if (!N) {
    N = parseInt(line);
  } else if (!K) {
    K = parseInt(line);
  } else {
    data = line.trim().split(" ").map(Number);
    count += 1;
  }
  if (count == 1) {
    rl.close();
  }
}).on("close", function () {
  console.log(solution(N, K, data));
  process.exit();
});