[백준 9655/javascript] 돌 게임

다이나믹 프로그래밍 문제

경우의 수를 처음부터 세어보면

Math.min(arr[i - 1] + 1, arr[i - 3] + 1)

위와 같은 점화식을 얻을 수 있다

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

9655번: 돌 게임

let input = [];

const readline = require("readline").createInterface({
  input: process.stdin,
  output: process.stdout,
});

readline.on("line", (line) => {
  input.push(line);
});

readline.on("close", () => {
  solution(input);
  process.exit();
});

const solution = (inp) => {
  let n = Number(inp[0]);
  let arr = Array(1004).fill(0);
  let ans;

  arr[0] = 0;
  arr[1] = 1;
  arr[2] = 2;

  for (let i = 3; i <= n; i++) {
    arr[i] = Math.min(arr[i - 1] + 1, arr[i - 3] + 1);
  }
  if (arr[n] % 2 === 1) {
    ans = "SK";
  } else {
    ans = "CY";
  }
  console.log(ans);
};