[node.js,백준]2133 - 타일 채우기

목차

 문제

링크

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

문제

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

입력

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

 

출력

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

 

주저리

쉽지않은 문제였다 정답을 보면서했다 ㅠ

풀이는 일단 마지막에 3이 채워지려면 2칸을 차지하는 3가지의 수가있다.

그리고 홀수들은 답이 되지못하는거 까진 알았다.

그럼 이제 짝수번부터 계산을 해야한다.

 

풀이

 입력 데이터 처리

• 파일 시스템 모듈(fs)을 사용하여 입력을 받습니다. 주석 처리된 부분은 실제 실행 환경에서 사용될 예정이며, 테스트를 위해 input 변수에 데이터를 직접 할당합니다.
• 입력 데이터는 문자열에서 숫자로 변환되어 처리됩니다.

 타일링 함수 testF

• arrays는 각 길이의 보드를 채울 수 있는 방법의 수를 저장합니다. 초기 값 arrays[1]은 1로 설정됩니다.
• 길이가 짝수일 때만 타일링이 가능하므로, 홀수 길이의 경우 0을 반환합니다.
• 길이가 2인 경우는 기본적으로 3가지 방법이 있습니다.
• 길이가 4 이상인 짝수의 경우, 동적 프로그래밍을 이용하여 이전 결과를 바탕으로 가능한 타일링 방법의 수를 계산합니다. 이 때, 3 * arrays[l]는 직전 값에 3배를 해주는 것으로 기본 2x1 또는 1x2 타일이 추가되는 경우를 고려합니다. 2 * arrays[l]은 특수한 타일링 형태가 추가되는 경우를 고려합니다.

 솔루션 함수 solution

• 입력 길이가 홀수인 경우, 타일링이 불가능하므로 0을 출력합니다.
• 짝수 길이의 경우, testF 함수를 호출하여 결과를 계산하고 출력합니다.

 코드

// 타일 채우기
var fs = require('fs');
// var input = fs.readFileSync('/dev/stdin').toString();
let input = `8`

let real = input.trim().split("\n");
let arrs = [1];
function testF(N, rest, arrays) {
    for (let i = 1; i <= N; i++) {
        if (i === 2) {
            arrays[i] = 3;
        }
        else if (i % 2 !== 0) {
            arrays[i] = 0;
        }
        else {
            arrays[i] = 0;
            // i === 4
            let l = i - 2;
            while (l !== -2) {
                // console.log({ l, i })
                if (l === (i - 2)) {
                    arrays[i] += 3 * arrays[l];
                } else {
                    arrays[i] += 2 * arrays[l];
                }
                l -= 2;
            }
        }
    }
}


function solution(real) {
    let [T, sec] = real;
    // let rest = sec.split(" ").map(Number);
    if (Number(T) % 2 !== 0) {
        console.log(0)
        return;
    }
    testF(Number(T), 0, arrs)
    console.log(arrs[arrs.length - 1])

}
solution(real);