[프로그래머스] 2 x n 타일링(12900)

1. 문제 풀이 아이디어

• 다이나믹 프로그래밍(DP)을 활용하여 문제를 해결할 수 있다.

2. 나의 정답 코드

class Solution {
    public int solution(int n) {
        int[] dp = new int[n + 2];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
        }
        return dp[n];
    }
}

3. 정리

• 길이가 1일 때 타일을 채우는 방법은 1가지이다.

• 길이가 2일 때 타일을 채우는 방법은 2가지이다.

• 그 이후는 길이-1에서 세로로 하나의 타일을 추가하는 경우와 길이-2에서 가로로 두 개의 타일을 추가하는 경우의 합으로 계산한다. 이를 다이나믹 프로그래밍으로 구현한다.

• 결과값은 문제 조건에 따라 1000000007로 나눈 나머지를 사용한다.

• nnn까지 반복한 후, 최종적으로 dp[n]을 반환하여 문제를 해결한다.