백준 11726 — 2×n 타일링: 마지막 타일을 기준으로 나누기

D[N] =
 // N번재 사각형을 만드는 경우의 수는, 마지막 타일을 기준으로 서로 겹치지 않는 두 집합으로
 // 분할이 가능하다
 // D[N-1]: 맨 끝 타일이 (2x1)의 세로 타일인 경우
 // D[N-2]: 맨 끝 타일이 (2x2)로 가로 타일 두 개를 쌓은 형태인 경우
 D[N-1] + D[N-2]

DP[N]의 모든 경우
│
├─ ① 마지막이 세로 타일
│      → 앞부분은 2×(N-1)
│      → DP[N-1]의 모든 경우
│
└─ ② 마지막이 가로 타일 2개
       → 앞부분은 2×(N-2)
       → DP[N-2]의 모든 경우

DP[1] = 1; // 2 x 1 사각형을 채우는 방법
DP[2] = 2; // 2 x 2 사각형을 채우는 방법

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const N = Number(fs.readFileSync(filePath, 'utf-8'));
 
function solution() {
    // 1.배열 생성하기
    const DP = Array.from({ length: N + 1 }).fill(0);
 
    // 2. 초기값 설정하기
    DP[1] = 1;
    DP[2] = 2;
 
    // 3. for문 순회하기
    for (let i = 3; i <= N; i++) {
        // 2 x i 의 사각형의 맨 끝 타일을 채우는 방법은 아래 두 개 밖에 없다.
        // 3-1) 맨 끝에 세로 타일이 오는 경우 (2 x 1) - DP[i - 1]
        // 3-2) 맨 끝에 가로 타일이 오는 경우 - DP[i - 2]
        DP[i] = (DP[i - 1] + DP[i - 2]) % 10007;
    }
 
    console.log(DP[N]);
}
 
solution();