[좋은문제]백준 2212: 센서 - javascript (그리디)

문제 출처 

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

2212번: 센서

문제

한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다.

각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다.

편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 하자. 따라서, 각 센서의 좌표는 정수 하나로 표현된다. 이 상황에서 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하는 프로그램을 작성하시오. 단, 집중국의 수신 가능영역의 길이는 0 이상이며 모든 센서의 좌표가 다를 필요는 없다.

입력

첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있으며, 좌표의 절댓값은 1,000,000 이하이다.

출력

첫째 줄에 문제에서 설명한 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력한다.

예제 입력 1 복사

6
2
1 6 9 3 6 7

예제 출력 1 복사

5

예제 입력 2 복사

10
5
20 3 14 6 7 8 18 10 12 15

예제 출력 2 복사

7

문제 풀이 힌트 

일단 문제 이해 부터 쉽지 않았다 

예시 1번의 경우를 보자 ! 

이때는 집중국의 수신 가능 영역의 길이의 합이 7이 된다! 

 

이렇게 k를 설치할 때는 

집중국의 수신 가능 영역의 길이의 합이 6이 된다! 

 

이렇게 k를 설치할 때는 

집중국의 수신 가능 영역의 길이의 합이 5가 된다!

문제에서 5가 최솟값이라 나온다!

눈치가 있다면  왜 이경우에서 최솟값이 나오는지 알 것이당 

=> 3과 6 사이의 차이가 제일 크니까, 그 부분이 스킵될 땨 k의 총합 길이가 최솟값이 된다. 

 

그런데 k를 어떻게 설치할까 고민하면 참 ~ 골치아파진다. 

이 문제는 센스가 필요했다. 

 

이 문제의 구성을 보자 

- 주어진 배열을 먼저 오름차순 정렬 한다 ([1,3,6,6,7,9])

- 각 요소의 차이를 구한 배열을 만든다.(dif = [2,3,0,1,2])

- 위 배열을 내림차순 정렬한다.([3,2,2,1,0])

- k가 2일 때는 1 구간을 건너뛸수 있고, k가 3일 때는 2구간을 건너뛸 수 있으니, 건너뛰는 개수의 idx 부터 다 더한다. 

[3,2,2,1,0] 한구간을 건너 뛸 땐 최솟값이 2+2+1+0 = 5가 된다 ! 

정답 풀이 코드 

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const N = +input[0]; 
const K = +input[1]; 
const sensor = input[2].split(' ').map(el=> Number(el)); 
function solution(N,K,sensor){
    sensor.sort((a,b)=> a-b);
    const dif = []; 
    for(let i=0; i<N-1; i++){
            dif.push(sensor[i+1]-sensor[i]);     
    }
    let answer = 0; 
    dif.sort((a,b)=> b-a)
    for(let i=K-1; i<N-1; i++){
        answer += dif[i]; 
    }
    return answer; 
}
const answer = solution(N,K,sensor)
console.log(answer);

의사 코드 추가

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const N = +input[0]; 
const K = +input[1]; 
const sensor = input[2].split(' ').map(el=> Number(el)); 
function solution(N,K,sensor){
    //오름차순 정렬
    sensor.sort((a,b)=> a-b);
    const dif = []; //각 요소 차이 구하는 배열
    for(let i=0; i<N-1; i++){
            dif.push(sensor[i+1]-sensor[i]);     
    }
    let answer = 0; 
    dif.sort((a,b)=> b-a) //차이 내림차순 정렬 (가장 크게 차이나는 것부터 제낄것임)
    for(let i=K-1; i<N-1; i++){ //k가 2개일땐 1개구간을 건너뛴다. k가 3일 땐 2개구간을 건너뛴다.
        answer += dif[i]; 
    }
    return answer; 
}
const answer = solution(N,K,sensor)
console.log(answer);