백준 25597 푸앙이와 러닝머신

문제

속력을 조작할 수 있는 버튼을 눌러 정확히 T를 맞추는 문제이다. 처음엔 완탐문제로 생각해서 백트래킹을 이용해서 최소한의 횟수를 구하려고 했다.

const INPUT_FILE =
  process.platform === "linux" ? "/dev/stdin/" : "./inputs.txt";
const [x, t] = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split(" ")
  .map(Number);
 
const runningButtons = [8, 4, 1, 0];
let minButton;
function backTrack(buttons, dist, sec) {
  if (sec > t || dist > x) return;
  if (dist === x && sec === t) {
    if (!minButton) {
      minButton = buttons;
      return;
    }
    if (minButton && buttons.length < minButton.length) {
      minButton = buttons;
    }
  }
  for (const b of runningButtons) {
    if (dist + b > x) continue;
    if (!buttons.length) {
      backTrack([[sec, b]], dist + b, sec + 1);
    } else if (buttons.at(-1)[1] === b) {
      backTrack(buttons, dist + b, sec + 1);
    } else {
      backTrack([...buttons, [sec, b]], dist + b, sec + 1);
    }
  }
}
backTrack([], 0, 0);
 
if (minButton) {
  console.log(minButton.length);
  console.log(minButton.map((b) => b.join(" ")).join("\n"));
} else {
  console.log(-1);
}
 

하지만 생각보다 시간이 길어지면서 훨씬 경우의 수가 많아지고 속도가 매우 느려제출할 수 없는 답안이었다. 가장 최소의 경우의 수를 구해야 한단 생각에 먼저 완탐부터 생각한게 패착이었다. 최소한의 버튼을 누르는 수에는 그리디도 있을 법한데 무조건 완탐으로만 하려고 하니 제대로 풀리지 않았던 것이었다. 결국 블로그의 힘을 빌려 풀었다. 근데 사실 풀이를 보고 다시 풀어봤어도 아직도 너무 어렵다.. 그리디란 그런걸까

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
let [n, k] = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split(" ")
  .map(Number);
 
let res8 = 0,
  res4 = 0,
  res1 = 0;
if (n >= 8) {
  res8 = Math.floor(n / 8);
  n %= 8;
}
 
if (n >= 4) {
  res4 = Math.floor(n / 4);
  n %= 4;
}
 
res1 = n;
 
let timeSum = res8 + res4 + res1;
if (timeSum > k) {
  console.log(-1);
  process.exit(0);
}
 
if (timeSum < k) {
  if (res8 > 0 && k - timeSum >= res8) {
    res4 += res8 * 2;
    res8 = 0;
    timeSum = res4 + res1 + res8;
  }
  if (res4 > 0 && k - timeSum >= res4 * 3) {
    res1 += res4 * 4;
    res4 = 0;
    timeSum = res1 + res4 + res8;
  }
}
const result = [];
if (res8 > 0) result.push([8, res8]);
if (res4 > 0) result.push([4, res4]);
if (res1 > 0) result.push([1, res1]);
console.log(result.length);
console.log(`${k - timeSum} ${result[0][0]}`);
let currTime = k - timeSum + result[0][1];
for (let i = 1; i < result.length; i++) {
  console.log(`${currTime} ${result[i][0]}`);
  currTime += result[i][1];
}
 

8,4,1 세 가지 경우로 x초 안에 갈 수 있는지 가장 처음에는 단순하게 각각 8,4,1순서대로 나눠서 계산해본다. 하지만 정확히 x초에 맞춰야 하므로 8,4,1로 나눴을 때 다 더한 시간이 벌써부터 높으면 이미 불가능한 시간이라는 의미이므로 -1일 출력하고 바로 끝낸다. 하지만 반대로 시간이 더 남는 경우는 다르다. 최대한 시간을 늘리면서도 버튼의 수를 줄여야 하므로 기존 초속 8짜리 버튼을 초속 4짜리 버튼으로 계산할 수 있는지 보거나 초속 4짜리 버튼을 초속 1짜리 버튼으로 바꿔서 사용했을 떄 기존의 시간보다 오래 걸리지 않는 이상 최대한 바꾸는 것이 이득이다.

k-timeSum >= res8과 k-timeSum >=res4*3은 이러한 이유에서 기존의 몫에 더해질 시간을 미리 계산해보는 것이므로 각각 2, 4배에서 1을 뺀 1,3을 곱한 값과 timeSum을 더한 값이 k를 넘지 않는지 계산한다.

이렇게 변환까지 끝냈으면 마지막에 결과를 출력해야 하는데 이것도 꽤나 까다로웠다. 각각 1번 이상 눌렀으면 결과 배열에 넣어주는데 처음에는 k-timeSum을 처음 result에 있는 첫번째 버튼을 누르는 초로 출력한 것이 보일 것이다. 이것은 다른걸 다 변환해도 시간이 남았을 때 가만히 있는 정지버튼(초속 0)을 눌렀을 때이며, 이를 처음에 미리 정지하다가 시작하도록 한다. 이후에는 계속 시간을 더해주며 결과를 출력해주면 된다.

골드의 벽…높다