문제

어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.

이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.

동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.

---

입력

첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.

---

출력

첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라.

---

입출력 예제

// 입력
4
// 출력
41

풀이

일단 아이디어는 DP 문제라고 유형이 나눠져있어서 금방 떠올렸다.

N = 1 일떄

이미지

이렇게 3 가지 경우가 있다.

N = 2 일 때

XX 밑으로 올 수 있는 경우는 XX XO OX 이다. (3가지!)

OX 밑으로 올 수 있는 경우는 XX XO 이다. (2가지!)

XO 밑으로 올 수 있는 경우는 XX OX 이다. (2가지!)

XX 일 때는 3가지 경우가 올 수 있고 OX, XO 일땐 2가지 경우가 올 수 있다.

그렇게 해서 3의 갯수랑 2의 갯수를 => [3의 갯수, 2의 갯수] 이렇게 저장하는 배열과

이 배열을 사용해서 3 3의 갯수 + 2 2의 갯수 % 9901 을 저장하는 배열을 만들어서 했는데 3이랑 2의 갯수가 너무 많아져서 Number 타입 범위를 벗어 났다..ㅠㅠ

이렇게 그려보니 규칙을 찾을 수 있었다.

dp[i] = dp[i - 1] * 2 + d[i -2] 를 볼 수 있었다.

---

코드

let input = `4`.trim();
// input = require('fs').readFileSync('/dev/stdin').toString().trim()
input = +input;

const dp = [0, 3, 7];

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