백준 2212 센서 js

2212번: 센서

문제 설명

문제 설명.

문제를 읽어보면 "집중국의 수신 가능 역역은 고속도로 상에서 연결된 구간을 나타나게 된다."라는 설명이 명시되어 있습니다.

 

즉. 특정 위치에 집중국을 설치하는 것이 아닌 "범위"로 수신 가능 영역을 조절하고 수신 가능 영역의 길이의 합을 최소화하는 문제입니다.

 

예제 1번을 예로 설명 이어가겠습니다.

예제 1.
6
2
1 6 9 3 6 7

편의상 센서의 위치를 오름차순으로 정렬하여 집중국 영역 2개로 나누어 영역의 길이 합을 최소화 하였을 때 다음과 같이 5가 정답이 됩니다. 

 

풀이.

예제 2번.
10
5
20 3 14 6 7 8 18 10 12 15

용어 정리.

센서와 인접한 센서의 거리 차이를 "거리 격차"라고 정의 하겠습니다.

 

풀이 순서.

1. 먼저 센서의 위치를 입력받아 오름차순으로 정렬한 뒤 [센서 위치, 거리 격차]로 "D"배열에 정리해 주겠습니다.

 

2. 거리 격차가 가장 큰 순서로 집중국 범위를 나누어 주어야 합니다. 주의할 점은 4번 나누어 주면 5개 구역으로나누어 지므로 입력받은 집중국 개수(K) - 1 만큼 나누어 주겠습니다.

 

위 예제에서 4번 나누어 줄 수있으니, 거리 격차가 가장 큰 3의 경우 두개를 나누어 주고, 나머지 두번은 거리 격차가 2인 센서 위치를 나누어 줍니다.

 

즉. "D"배열을 "거리 격차" 기준으로 내림차순 정렬 후 나눌 수 있는 횟수 만큼 잘른 후 "센서 위치"를 기준으로 오름 차순 정렬 후 "S"배열에 새로 할당해 줍니다.

 

3. 이제 나누어진 센서의 위치를 제외한 나머지 센서들의 거리 격차를 구간 별로 더하면 정답을 구할 수 있습니다.

 

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

let N, K;
let input = [];

rl.on("line", function (line) {
  if (!N) {
    N = +line;
  } else if (!K) {
    K = +line;
  } else {
    input = line.split(" ").map(Number);

    rl.close();
  }
}).on("close", function () {
  let result = 0; // 정답을 담을 변수
  input.sort((a, b) => a - b);
 
  let D = []; // 거리 격차를 담을 배열
  for (let i = 1; i < N; i++) {
    const gap = input[i] - input[i - 1];
    D.push([i - 1, gap]);
  }
  
  // 집중국의 수신 가능 영역을 나눌 특정 위치를 담을 배열
  // K - 1번 나누어 주면 K개 영역으로 나눌 수 있으므로 K - 1번 
  // 나누어 주고, 위치를 기준으로 오름차순 정렬
  // 수신 가능 영역별로 거리를 구하기 위해 반드시 마지막 위치또한 
  // 포함되어 있어야 하므로, [마지막 위치, 의미없는 값]을 push
  S = [...D]
    .sort((a, b) => b[1] - a[1])
    .slice(0, K - 1)
    .sort((a, b) => a[0] - b[0]);
  S.push([N - 1, 0]);
  
  let index = 0;
  let start = 0;
  while (index < S.length) {
    const [end, _] = S[index++];
    for (let i = start; i < end; i++) {
      // D배열은 센서들의 거리 격차를 담고 있는 배열입니다.
      // S에 담긴 수신 가능 영역으로 나눌 위치를 기준으로 
      // 수신 가능 영역별로 거리를 정답에 더해줍니다.
      result += D[i][1];
    }
    start = end + 1;
  }

  console.log(result);
  process.exit();
});

 

그리디 알고리즘과 정렬 알고리즘이 요구되는 문제였습니다.