🔎 2xn 타일링

❓ 문제링크

https://programmers.co.kr/learn/courses/30/lessons/12900

📄 제출 코드

function solution(n) {
    let dp = Array(n).fill(0);
    dp[1] = 1;
    dp[2] = 2;
    for (let i= 3; i <= n; i++) {
        let tmp = dp[i - 1] + dp[i - 2];
        dp[i] = tmp %1000000007;

    }
    var answer = dp[n];
    return answer;
}
let n = 4;
console.log(solution(n));

가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일을 가지고, 세로가2, 길이가 n인 바닥을 채우려고 할 때 방법 수를 세는 문제.
일단 방법 수 부터 생각했다.
case 1: | 1
case 2: || , ㅡ를 쌓는방법. 2
case 3: |||, | 세우고(좌) ㅡ두개 쌓기,|세우고(우) ㅡ두개 쌓기 3
case 4: 문제에 그림보여줌. 5
case 5 : 8
....
여기서 '1 2 3 5 8 ...'를 보자.
그럼 피보나치 수열이 보일 것 이다.
n의 범위가 6만까지라서 숫자가 너무 커질 수 있어 결과를 1000000007로 나눈 값을 저장하라고 문제에 나와있으니 주의!

📘 참고

https://velog.io/@diddnjs02/코딩테스트프로그래머스-2xn-타일링