[node.js] 백준 1309 동물원

로직

• 동물을 윗 칸부터 아래로 채워가는 형태로 생각

• 동물을 배치하는 방법은 기본적으로 3가지(배치x, 왼쪽 배치, 오른쪽 배치)

• 배치를 안할 경우 윗칸에 동물 여부에 상관 없음

• 왼쪽에 배치할 경우 윗칸에 배치가 안되었거나, 왼쪽에 배치되어 있어야 함

• 오른쪽에 배치할 경우 윗칸에 배치가 안되었거나, 오른쪽에 배치되어 있어야함

• 그렇기에 배치를 안한 경우의수, 왼쪽에 배치한 경우의 수, 오른쪽에 배치한 경우의 수를 계산해야함

• 배치를 안한 경우의 수는 윗칸 모든 경우의 수(배치를 안한 경우 + 왼쪽에 배치한 경우 + 오른쪽에 배치한 경우)

• 왼쪽에 배치하는 경우의 수는 윗칸에서 (배치를 안 한 경우 + 오른쪽에 배치한 경우)

• 오른쪽에 배치하는 경우의 수는 윗칸에서 (배치를 안 한 경우 + 왼쪽에 배치한 경우)

• 이를 누적해가며 계산하는 방식

• 현재 칸에서 계산이 끝난 경우, 윗칸의 경우의 수는 더 이상 쓸모가 없음 => 메모리 낭비

  • 그렇기에 기록하는 배열을 N*3이 아닌 2*3으로 만들어 메모리 낭비를 줄임

const solution = (N,mod)=>{
    const dp = Array.from({length:2},()=>Array.from({length:3}).fill(1));
    for (let cnt=1;cnt<=N;cnt++){
        const [bi,ni] = [(cnt-1)%2,cnt%2];
        dp[ni][0] = (dp[bi].reduce((total,value)=>total+value,0))%mod;
        dp[ni][1] = (dp[bi][0] + dp[bi][2])%mod;
        dp[ni][2] = (dp[bi][0] + dp[bi][1])%mod;
    };
    return dp[N%2][0];
}

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
let N;
const mod = 9901;
rl.on('line', (line) => {
    N = parseInt(line);
    rl.close();
});
rl.on('close', () => {
  const ans = solution(N,mod);
  console.log(ans);
});

후기

• readline을 사용해보려고 했으나, 이번 문제의 경우 N 단 한가지 값만 존재하다 보니 의미가 없어서 써야하나 했지만, 써보기로 했으므로 일단 사용했다
• for of 구문에서 const 선언을 주로 사용하다 보니 const cnt를 선언하고 왜 작동을 안하지? 라는 의문이 생겼었다... javascript가 익숙해질 때 까지 많이 남았다.