백준 15553 난로

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

문제

난로를 가장 조금 킬 수 있는 방법을 찾는 문제이다.

예제를 보자

input
3 2
1
3
6

answer 4

해당 예제에서는 3명의 친구가 오고, 2개의 성냥이 있다.

1 2 3 4 5 6이 있다고 할 때, 친구는 Ti +1시간까지 구사과의 방에 머물기 때문에 1, 2, 3, 4, 6, 7 에는 무조건 난로가 켜져 있어야 한다. 따라서 1시에 키고 4시에 끈 다음, 다시 6시에 키면 된다.

이렇게 최소한의 난로가 켜져 있는 시간을 구하기 위해서는, 다른 친구들과의 간격이 긴 친구들 먼저 뽑아내어 얘네만 따로 난로를 켜야 한다. 간격이 넓을 수록 시간이 더 길어지기 때문이다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const inputs = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
 
let [n, k] = inputs[0].split(" ").map(Number);
const times = inputs.slice(1).map(Number);
 
const gaps = [];
let totalTime = times[n - 1] + 1 - times[0];
 
for (let i = 1; i < n; i++) {
  gaps.push(times[i] - times[i - 1] - 1);
}
 
gaps.sort((a, b) => b - a);
 
for (let i = 0; i < k - 1; i++) {
  totalTime -= gaps[i];
}
 
console.log(totalTime);

따라서 맨 처음에는 처음부터 끝까지 한 번도 난로를 안 껐을 때 걸린 시간에서 각 친구들간의 시간을 구한 다음에 단축되는 간격만큼을 빼주면 된다.