2xN 타일링

문제 설명

가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.

• 타일을 가로로 배치하는 경우
• 타일을 세로로 배치하는 경우
  직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

제한사항

• 가로의 길이 n은 60,000이하의 자연수 입니다.
• 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

입출력 예

n = 4
result = 5

문제 풀이

function solution(n) {
    var answer = 0;
    let dp = new Array(n + 1).fill(0);
    dp[0] = 1
    dp[1] = 1
    for (let i = 2; i <= n; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
    }
    answer = dp[n]
    return answer;
}

아이디어 / 접근법

먼저 타일이 어떻게 증가하는 지 손으로 작성해보니 이전의 값과 2번째 전의 값을 더하면 값이 나오는 전형적인 피보나치 수열 DP 였음 따라서 값을 구하고 나머지 연산을 통해 결과를 도출했음

후기

전형적인 DP 문제였고 직접 손으로 규칙을 찾아보니 문제 푸는 데에는 어려움이 없었음