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

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

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

 

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

dp[depth] = dp[depth -1] + dp[depth -2] 공식을 세워 dp를 풀었습니다.

 

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;
    }
}