[코드트리 조별과제] 사각형 채우기3

문제링크
코드트리 조별과제로 코테 공부 좀 해볼까? 매주 글만써도 한달 정도는 무료니까 너무 좋을 것 같다. 오늘은 dp를 풀었다. 백준엔 없는 문제라 좋은듯!

전에 보았던 사각형 채우기 문제보다 경우의 수가 많아져서 더 어렵게 느껴졌던 문제이다.
하지만! 점화식 구하고 나면 너무 쉽게 보인다. 해설을 올리고 싶지만 해설 캡처는 안되는 것 같다.

문제는 대충 2xn의 사각형을 채우는데 어떤 사각형이냐면 2x1, 1x1, 1x2인 사각형으로 채우면 된다.

i-1일 때, 채울 수 있는 사각형의 크기는 2x1이고 2x1, 1x1 2개가 있다. 그러므로 2가지이다.
i-2일 때, 채울 수 있는 사각형의 크기는 2x2이고 2x1 2개, 1x2 2개, 1x1 4개로 3가지가 있다.
i-3일 때, 채울 수 있는 사각형의 크기는 2x3이고 앞의 경우를 제외하고 2가지 있다.
계속 구해보면 i-3부터는 2가지 경우만 나오는데 이것을 점화식으로 세우면 된다.

풀이

const fs = require('fs');
const n = fs.readFileSync(0).toString();

const dp = Array(1001).fill(0)

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

for (let i = 3; i <= 1000; i++) {
    dp[i] = (dp[i-1] * 2 + dp[i-2] * 3 + dp.slice(0,i-2).reduce((sum,value) => sum + value, 0) * 2) % 1000000007
}

console.log(dp[+n])