백준 15553 난로

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

문제 설명

문제

구사과의 방에는 난로가 하나 있다. 구사과는 절약 정신이 투철하기 때문에, 방에 혼자 있을 때는 난로를 되도록 켜지 않는다. 구사과는 방에 친구가 왔을 때는 항상 난로를 켠다.

오늘은 N명의 친구들이 구사과의 집에 방문하는 날이다. 구사과는 친구들을 쉽게 구분하기 위해 1부터 N까지 번호를 매겼다. i번째 친구는 구사과의 방에 시간 Ti에 도착하고, 시간 Ti+1에 나간다. 구사과의 방은 좁기 때문에, 한 번에 한 명만 방문할 수 있다. 즉, 방안에는 항상 구사과를 포함해 2명 이하의 사람만 있게 된다.

구사과는 난로를 아무 때나 켤 수 있고, 끌 수 있다. 난로를 켜려면 성냥을 이용해야 한다. 오늘 구사과는 총 K개의 성냥을 가지고 있다. 따라서, 최대 K번 난로를 켤 수 있다. 가장 처음에 난로는 꺼져있다.

구사과는 난로가 켜져 있는 시간을 최소로 하려고 한다. 구사과의 친구들이 도착하는 시간과 가지고 있는 성냥의 개수가 주어졌을 때, 난로가 켜져 있는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 구사과의 집을 방문하는 친구의 수 N (1 ≤ N ≤ 100,000), 구사과가 가지고 있는 성냥의 개수 K (1 ≤ K ≤ N)이 주어진다.

둘째 줄부터 N개의 줄에는 구사과의 집을 방문하는 친구의 도착 시간 Ti가 i가 증가하는 순서대로 주어진다. (1 ≤ Ti ≤ 1,000,000,000) 동시에 두 명이 방문하는 경우는 없기 때문에, 모든 1 ≤ i ≤ N-1에 대해서 Ti < Ti+1 를 만족한다.

출력

첫째 줄에 난로가 켜져 있는 시간의 최솟값을 출력한다.

---

문제 풀이

bfs를 이용해 현재 초를 킬 경우와 안 킬 경우를 계산해 최소 값을 구하도록 함 bfs를 이용해 풀 경우 20점이 나옴 (다른 방법으로 접근해서 풀어야함)

const inputs = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

// n : 1 ~ 100000, k : 1 ~ 1,000,000,000
const [n, k] = inputs[0].split(" ").map(Number);
const n_list = inputs.slice(1).map(Number);

// 난로의 최소 값 구하기
let answer = Infinity;

// 초를 킬 수 있는 횟수가 n - 1개보다 크면 그냥 n 초 리턴
if (k >= n) {
  console.log(n);
  return;
}

// 최소 시간 계산
// 검사할 위치, 초를 킨 시간, 초를 끈 시간, 총 시간, 초를 킨 횟수
let tmp = [[0, n_list[0], n_list[0] + 1, 0, 1]];
let tmp_index = 0;

const precess = () => {
  while (tmp_index < tmp.length) {
    let [start, turnOnTime, turnOffTime, total_time, turnOnCount] =
      tmp[tmp_index++];
    // 초를 더 킬 수 있을 경우
    if (turnOnCount < k) {
      // 다음 사람이 있을 경우
      if (start + 1 < n) {
        // answer보다 현재 초를 킬 경우 시간이 더 작다면 초를 킴
        if (answer > total_time + turnOffTime - turnOnTime) {
          // 초를 킬 경우
          tmp.push([
            start + 1,
            n_list[start + 1],
            n_list[start + 1] + 1,
            total_time + turnOffTime - turnOnTime,
            turnOnCount + 1,
          ]);
        }
        //초를 안 킬 경우
        tmp.push([
          start + 1,
          turnOnTime,
          n_list[start + 1] + 1,
          total_time,
          turnOnCount,
        ]);
      } else {
        answer = Math.min(
          answer,
          total_time + n_list[n_list.length - 1] + 1 - turnOnTime
        );
      }
    } else {
      answer = Math.min(
        answer,
        total_time + n_list[n_list.length - 1] + 1 - turnOnTime
      );
    }
  }
};

precess();

console.log(answer);

 

그리디, 정렬을 이용하여 풀이 (100점)

사람과 사람사이의 난로가 꺼져있는 시간을 구하고 해당 값이 클 경우 바로 끌 수 있도록 하면 난로를 키는 시간을 최소화할 수 있음

const inputs = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

// n : 1 ~ 100000, k : 1 ~ 1,000,000,000
let [n, k] = inputs[0].split(" ").map(Number);
const n_list = inputs.slice(1).map(Number);

// 난로가 꺼져있는 시간 찾기 -> 특정 2명 사이 값 - 1이 꺼져있는 시간임
// ex. 15 16 일 경우 두 사람 사이의 난로가 꺼지는 시간은 16 - 15 - 1 = 0임
let turnOffTime = [];
for (let i = 1; i < n; i++) {
  turnOffTime.push(n_list[i] - n_list[i - 1] - 1);
}

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

// k-1개를 1초만에 바로 끄고 나머지는 켜두면 최소시간이 되므로
// 꺼져있는 시간이 가장 큰 k - 1개를 골라 전체 크기에서 빼면 최소 시간이 됨
let maxTurnOffTime = 0;
while (k > 1) {
  maxTurnOffTime += turnOffTime.pop();
  k--;
}

console.log(n_list[n - 1] + 1 - n_list[0] - maxTurnOffTime);

---

결론

완전 탐색 느낌이나도 특정 규칙으로 답을 찾는 연습을 더 해야할 것 같음.