2133 타일 채우기

문제

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

출력

첫째 줄에 경우의 수를 출력한다.

=====

문제 분석

1*2, 2*1 타일들을 조합하여 세로의 길이가 3이고 가로의 길이가 n인 직사각형을 채우는 경우의 수를 출력하는 문제이다.

만약 이 문제가 세로의 길이가 2였다면 

가로의 길이를 인덱스로 한 배열을 선언하고 , dp[i] = dp[i-1] + dp[i-2] 가 나올 것이다.

(직전 타일 가로 길이에서 타일 세로로 세워서 1개 추가하고, 두개 직전의 타일 갯수에서 가로로 눕힌 타일을 붙이니까)

이 문제가 위의 경우와 다른 이유는 세로의 길이가 3이라는 것이다.

가로의 길이가 홀수라면, 타일을 어떻게 채우든 빈 위치가 생겨서 답이 되지 않는다.

    if (n % 2 !== 0) {
        console.log(0);
        process.exit(0);
    }

가로 길이가 1이라면 1*2를 세로로 세우는 방법이 있지만 이 떄의 세로 길이는 2가 되어 위나 아래에 타일을 가로로 눕힌 것을 추가해야한다. 물론 이렇게 세운다면 빈 위치가 생겨서 정답의 조건은 되지 않지만 이후의 가로의 길이들을 측정할 때 사용하기 위해 기록해둔다.

가로의 길이가 2라면,

1) 위에서 만든 가로 길이 1에서 세로로 세운 타일을 하나씩 추가한다 -> dp[1]

2) 가로로 눕힌 1*2 타일 3개를 쌓는다. -> 1

가로의 길이가 3이라면 

1) 가로 길이가 2에서 1개를 추가로 세우지만 위아래로 눕힌 타일도 추가해야한다 -> dp[2]*2

2) 가로 길이가 1에서 가로로 눕혀서 3개를 쌓은 타일을 추가한다 ->dp[1] 

가로의 길이가 4라면

1) 가로 길이가 3에서 1개를 추가로 세우지만 위아래로 눕힌 타일도 추가해야한다 -> dp[3]

2) 가로 길이가 2에서 가로로 눕혀서 3개를 쌓은 타일을 추가한다 ->dp[2] 

위를 통해 홀수와 짝수의 경우를 따로 두어 점화식을 세울 수 있다

const dp = Array.from({ length: n + 1 }).fill(0);
dp[1] = 2;
dp[2] = 3;
dp[3] = 8;
for (let i = 4; i < n + 1; i++) {
    if (i % 2 === 0) {
        dp[i] = dp[i - 1] + dp[i - 2];
    } else {
        dp[i] = dp[i - 1] * 2 + dp[i - 2];
    }
}

정답 코드

const main = (n) => {
    if (n % 2 !== 0) {
        console.log(0);
        process.exit(0);
    }
    const dp = Array.from({ length: n + 1 }).fill(0);
    dp[1] = 2;
    dp[2] = 3;
    dp[3] = 8;
    for (let i = 4; i < n + 1; i++) {
        if (i % 2 === 0) {
            dp[i] = dp[i - 1] + dp[i - 2];
        } else {
            dp[i] = dp[i - 1] * 2 + dp[i - 2];
        }
    }

    console.log(dp[n]);
};

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const [n] = input[0].split(' ').map((v) => +v);
main(n);