백준 14677 병약한 윤호

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

문제

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const [a, meds] = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
 
const day = +a;
const order = ["B", "L", "D"];
const medicine = meds.split("");
 
let max = 0;
function getMaxMedicineCount(ggini, left, right) {
  if (ggini / 3 === day || left > right) return;
  if (order[ggini % 3] === medicine[left]) {
    max = Math.max(max, ggini + 1);
    getMaxMedicineCount(ggini + 1, left + 1, right);
  }
  if (order[ggini % 3] === medicine[right]) {
    max = Math.max(max, ggini + 1);
    getMaxMedicineCount(ggini + 1, left, right - 1);
  }
}
getMaxMedicineCount(0, 0, medicine.length - 1);
console.log(max);

처음에는 투포인터 느낌으로 재귀를 돌면서 하면 되겠다고 생각했는데 채점 과정에서 18퍼센트쯤에서 시간초과가 났다.

그래서 조금 더 다른 방식으로 로직을 짜서 개선해볼까 하는 생각에 BFS를 이용한 방식을 사용해보았다.

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const [a, meds] = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
 
const day = +a;
const order = ["B", "L", "D"];
const medicine = meds.split("");
 
let max = 0;
const queue = [[0, 0, medicine.length - 1]];
while (queue.length) {
  const [ggini, left, right] = queue.shift();
  max = Math.max(max, ggini);
 
  if (ggini / 3 === day || left > right) continue;
 
  if (order[ggini % 3] === medicine[left]) {
    queue.push([ggini + 1, left + 1, right]);
  }
  if (order[ggini % 3] === medicine[right]) {
    queue.push([ggini + 1, left, right - 1]);
  }
}
 
console.log(max);
 

효과는 미미했다…

기존 bfs 방식의 문제점은 내가 이제까지 갔던 길을 다시금 처음부터 탐색해야 한다는 점이었다

const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const [a, meds] = require("fs")
  .readFileSync(INPUT_FILE)
  .toString()
  .trim()
  .split("\n");
 
const day = +a;
const order = ["B", "L", "D"];
const medicine = meds.split("");
const visited = new Set();
 
let max = 0;
const queue = [[0, 0, medicine.length - 1]];
while (queue.length) {
  const [ggini, left, right] = queue.shift();
  max = Math.max(max, ggini);
 
  if (ggini / 3 === day || left > right) continue;
 
  const key = `${ggini}_${left}_${right}`;
  if (visited.has(key)) continue;
  visited.add(key);
 
  if (order[ggini % 3] === medicine[left]) {
    visited[left] = true;
    queue.push([ggini + 1, left + 1, right]);
  }
  if (order[ggini % 3] === medicine[right]) {
    visited[right] = true;
    queue.push([ggini + 1, left, right - 1]);
  }
}
 
console.log(max);

이전까지 갔던 경로를 Set으로 메모이제이션하고 막아놨다. 어차피 끼니, 좌 우 위치가 같으면 결국 같은 최댓값이 탐색될 것이기 때문이다. 이렇게 개선한 이후에는 다시 시간이 개선되어 정답이 나왔다.