[백준][dp] 1309 동물원 NodeJs 구현

목차

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

문제

문제 구현 방향

ox -> 0

xo -> 1

xx -> 2

라고 하면 0일때는 다음에 1 2, 1일때는 다음에 0, 2 2일때는 다음에 0, 1, 2 가 올 수 있다.

따라서 다음과 같이 점화식이 세워진다.

 

  let a = (dp[1] + dp[2]) % md;
  let b = (dp[0] + dp[2]) % md;
  let c = (dp[1] + dp[2] + dp[0]) % md;

 

문제 구현 시 주의점

이 문제는 그 전 것만 누적하면 되기때문에 배열에 모든 과정의 값들을 저장할 필요가 없다.

 

 

코드 구현

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");

let N = +input[0];
let md = 9901;
let dp = [1, 1, 1];

for (let i = 2; i <= N; i++) {
  let a = (dp[1] + dp[2]) % md;
  let b = (dp[0] + dp[2]) % md;
  let c = (dp[1] + dp[2] + dp[0]) % md;
  dp = [a, b, c];
}
let ans = dp.reduce((cur, el) => cur + el, 0);
console.log(ans%9901);