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

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

1309번: 동물원

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

let input;

rl.on('line', function (line) {
  input = +line;
  rl.close();
}).on('close', function () {
  const dp = [];

  dp[0] = 0;
  dp[1] = 3;
  dp[2] = 7;
  dp[3] = 17;

  for (let i = 4; i <= input; i++) {
    dp[i] = (dp[i - 1] * 2 + dp[i - 2]) % 9901;
  }

  console.log(dp[input] % 9901);
});

전형적인 DP문제이다. DP문제는 메모리제한이 낮거나, 입력값이 상당히 크다면 DP문제인지 파악해보자.

 

N = 0일때는 당연히 사자가 들어갈 공간이 없으므로 0이다.

 

N = 1일때는 2X1 공간이 있으므로

사자가 없는경우 => 1

사자가 한 마라인 경우 2 => 3이다.

 

N = 2일때는 2X2 공간이 있으므로

사자가 없는경우 => 1

사자가 한 마리인 경우 => 4

사자가 2마리인 경우 => 2 => 7이다.

 

N = 3일때는 2X3의 공간이 있으므로

사자가 없는경우 => 1

사자가 한 마리인 경우 => 6

사자가 2마리인 경우 => 8

사자가 3마리인 경우 => 2   => 17이다.

 

여기까지 보면 점화식을 유추할 수 있다.

결국 2X3의 공간은 2X2의 공간이 중복없이 2개 들어가고 2X1의 공간이 하나 들어갈 수 있다.

 

Fun(N) = Fun(N-1)*2 + Fun(N-2) 이란 걸 알 수 있다!

 

%9901에 유의하며 답을 내면 끝이다.