[백준1309_자바스크립트(javascript)] - 동물원

🔴 문제

동물원

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const n = Number(fs.readFileSync(path).toString().trim());
const dp = Array.from({ length: n + 1 }, () => [0, 0, 0]);
const mod = 9901;

dp[1] = [1, 1, 1];

for (let i = 2; i <= n; i++) {
  dp[i][0] = (dp[i - 1][1] + dp[i - 1][2]) % mod;
  dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % mod;
  dp[i][2] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % mod;
}

console.log(dp[n].reduce((pre, cur) => pre + cur, 0) % mod);

🟢 풀이

⏰ 소요한 시간 : -

DP 유형의 문제다. 점화식만 찾으면 쉽게 풀 수 있는 문제
n번째 줄에 사자를 배치할 수 있는 경우를 3가지로 나누어 고려해주면 된다. 왼쪽, 오른쪽, 배치안함
이 경우 1번째 줄에는 왼쪽에 배치하는 경우, 오른쪽에 배치하는 경우, 배치를 안하는 경우 각각 한가지씩 고려해주면 된다.
2번째 줄부터는 왼쪽에 배치할 수 있는 경우의 수는 이전단계에서 오른쪽에 배치했거나, 배치를 안했거나이다.
오른쪽에 배치할 수 있는 경우의 수는 이전단계에서 왼쪽에 배치했거나, 배치를 안했거나이다.
배치를 안 할 경우의 수는 이전에서 어떤 배치를 하든 상관없다.

따라서 점화식은 다음과 같이 세울 수 있다.

dp[i][0] = (dp[i - 1][1] + dp[i - 1][2]) % mod;
dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % mod;
dp[i][2] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % mod;

마지막까지 mod연산을 꼬옥 해주자.

🔵 Ref