[백준] 13164번: 행복 유치원 (JavaScript, NodeJS)

문제

행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다.

이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다. 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양이를 도와 최소의 비용을 구하자.

입력

입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들의 키를 나타내는 N개의 자연수가 공백으로 구분되어 줄 서 있는 순서대로 주어진다. 태양이는 원생들을 키 순서대로 줄 세웠으므로, 왼쪽에 있는 원생이 오른쪽에 있는 원생보다 크지 않다. 원생의 키는 109를 넘지 않는 자연수이다.

출력

티셔츠 만드는 비용이 최소가 되도록 K개의 조로 나누었을 때, 티셔츠 만드는 비용을 출력한다.

예제 입력 1 복사

5 3
1 3 5 6 10

예제 출력 1 복사

3

정답 풀이

const path = process.platform === "linux" ? "/dev/stdin" : "input.txt"; // 리눅스로 테스트할 땐 따로 설정해주어야 합니다.
const input = require("fs").readFileSync(path).toString().trim().split("\n");

let [n, tall] = input;
const [N, K] = n.split(' ').map(i => +i);
tall = tall.split(' ').map(i => +i);

// 문제 풀이
function solution(N, K, tall) {
	let answer = 0;
	const diff = [];

	// 각 원소들의 차이를 구해서 배열에 넣습니다.
	for (let i = 0; i < N - 1; i += 1) {
		diff.push(tall[i + 1] - tall[i]);
	}

	// 차이 배열을 오름차순 정렬합니다.
	diff.sort((a, b) => a - b);

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

	return answer;
}

// 제출
const answer = solution(N, K, tall);
console.log(answer);

⭐ 문제 핵심 아이디어 ⭐
1. 그리디
2. 각각의 원소들의 차이(diff) 배열을 구한다.
3. 차이의 배열을 오름차순 정렬한다. 
4. 최소값을 구하기 위해 앞에서부터 diff.length - ( k - 1 ) 만큼의 원소를 다 더한다.