[백준] 0923 오늘의 문제 풀이📚

오늘도 타일링 문제를 풀었는데

점화식에 변화구가 생겼다 ㅋㅋ

아니 뭐 어떻게 풀라는 건지 ㅋㅋ

사람들은 이걸 어떻게 푸는건지 ㅋㅋ

내가 멍청한건가 ㅋㅋ

바로 해답봤네 ㅋㅋ

아오 ㅋㅋ

 

1. 타일 채우기

문제 링크

var input = [];
const readline = require('readline');
const fs = require('fs');

const r = readline.createInterface({
    input: process.stdin
});

r.on('line', function(line) {
    input.push(line.trim());
});

r.on('close', function() {
    const n = Number(input[0]);
    const m = new Array(31).fill(0);

    function tile(x) {
        if(x === 0) return 0;
        if(x === 2) return 3;
        if(x % 2 === 1) return 0;
        if(m[x] !== 0) return m[x];

        let result = 3 * tile(x - 2);
        for(let i = 2; i <= x/2<<0; i++) {
            result += 2 * tile(x - 2*i);
        } 
        m[x] = result;
        return m[x];
    }

    console.log(tile(n));
});

f(n) = 3 * f(n - 1) + 2 * (f(n - 2) + f(n - 3) + ... )

이런 점화식이었는데..

익숙해지면 그리 어렵진 않은 점화식인거같긴 한데

처음 접하는 입장에서는 도저히 뭐 생각지도 못한 점화식이었다..