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

문제 링크

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

풀이 과정

N이 1일 때, 2일 때는 위와 같이 직사각형을 채울 수 있습니다.

N이 3일 땐, 가로가 1일 때와 2일 때의 직사각형에 타일을 덧붙여 모양을 만들 수 있습니다. 따라서, 아래와 같은 점화식을 세울 수 있습니다.

$$dp[i]=\begin{cases}1, &\mbox{i=1}\\2, &\mbox{i=2}\\dp[i-1]+dp[i-2], &\mbox{i $\ge$ 3} \end{cases}$$

코드

public class Main {
    public static long solution(int n) {
        final int MOD = 1_000_000_007;

        if (n <= 2) return n;

        long[] dp = new long[n + 1];
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; i++) dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;

        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(solution(4));
    }
}