[백준] 0922 어제의 문제 풀이📚

동적계획법에 도전해봤는데..

벽을 느껴버렸다..

점화식 세우는게 너무 어렵네 ㅋㅋ;

일단 개념은 대충 알았으니까 예제 계속 풀면서 유형을 좀 익혀야겠다..

 

- 동적 계획법 = 분할정복 + 메모이제이션

- 메모이제이션을 위해서는 배열을 만들어서, 입력값에 해당하는 index에다가 결과값을 저장해야 함

- n일 경우에 어떤 식이 나오는지를 n-1, n-2 등과 비교하면서 점화식을 세워야 함

 

1. 2xn 타일링

문제 링크

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 = BigInt(input[0]);

    const m = new Array(1001).fill(0);

    function tile(x) {
        if(x == 1) return BigInt(1);
        if(x == 2) return BigInt(2);
        if(m[x] != 0) return m[x];
        
        m[x] = (tile(x-BigInt(1)) + tile(x-BigInt(2))) % BigInt(10007);
        return m[x];
    }

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

아유 BigInt 넘나 귀찮은거..

 

2. 2xn 타일링 2

문제 링크

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 = BigInt(input[0]);

    const m = new Array(1001).fill(0);

    function tile(x) {
        if(x == 1) return BigInt(1);
        if(x == 2) return BigInt(3);
        if(m[x] != 0) return m[x];
        
        m[x] = (tile(x-BigInt(1)) + BigInt(2) * tile(x-BigInt(2))) % BigInt(10007);
        return m[x];
    }

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

메모이제이션용 배열은 반드시 0으로 초기화하는 것 잊지말자.

fill(0) 안해주면 결과가 undefined로 나오니깐..