백준 11726 : 2 x n 타일링

💡기본 정보

유형
: DP
풀이 날짜
: 2025년 01월 30일 
풀이방법 한줄 요약
: bottom-up형식으로 점화식 세워서 구현

 

💡문제에서 구해야 할 것

2*n 크기의 직사각형을 1*2 , 2*1 타일로 채우는 방법의 수를 구하는 프로그램
- 입력 : 첫째 줄에 n이 주어짐
- 출력 : 첫째 줄에 2*n크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지 출력

 

💡알고리즘 설계

- Bottom-up 방식으로 반복문 구현
- dp[1] = 1

- dp[2] = 2

- dp[3] = 3

- dp[4] = dp[3] + dp[2] = 5

     => dp[N] = dp[N-1] + dp[N-2] : 점화식

💡CODE

const fs = require("fs");
const N = Number(fs.readFileSync(0,"utf8").toString().trim());
const dp = new Array(N+1);

function tile(){
    dp[1] = 1;
    dp[2] = 2;
    for(let i = 3 ; i<=N; i++){
        dp[i] = (dp[i-1] + dp[i-2])%10007;
    }
    return dp[N];
}

console.log(tile());

 

💡시간복잡도

 

💡 틀린 이유 & 틀린 부분 수정

- 

 

💡 다른 풀이 or 기억할정보

-