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

문제

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

코딩테스트 연습 - 2 x n 타일링

 

풀이

DP 방식으로 풀 수 있다. 코드는 정말 간단한데 점화식을 세우는 게 쉽지 않다.

타일이 가로로 끝나는 것과 세로로 끝나는 것을 분류해보면 아래와 같다. 

DP[i] = DP[i-1] + DP[i-2]

가로길이가 i일 때, 타일링의 경우의 수는 = i-1의 경우의 수와 i-2의 경우의 수를 합한 것이다. 

i-1의 경우의 수에서 세로 타일을 붙임

i-2의 경우의 수에서 가로 타일을 붙임

 

소스코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        int[] dp = new int[n+1];
        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];
    }
}