프로그래머스 2xn타일링 (JAVA)

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

프로그래머스

 

저는 DP를 이용하여 문제를 해결하였습니다.

1과 2는 미리 초기화 시켜주었습니다.

dp[depth] = (dfs(depth-1,dp) + dfs(depth-2,dp)) 이렇게 공식이 나온 이유는 세로로 하나 넣으면 한칸만 차지하고, 가로로 2개 넣으면 2칸 차지하기 때문입니다.

 

class Solution {
    private static final int LIMIT = 1_000_000_007;
    private static final int NOT_VALID = 0;
    public int solution(int n) {
        int answer = 0;
        int[] dp = new int[n +1];
        answer = dfs(n,dp);
        return answer;
    }
    private int dfs(int depth, int[] dp){
        if(dp[depth] != NOT_VALID){
            return dp[depth];
        }
        if(depth == 1){
            return 1;
        }
        if(depth == 2){
            return 2;
        }
        return dp[depth] = (dfs(depth-1,dp) + dfs(depth-2,dp)) % LIMIT;
    }
}