[프로그래머스] 2xN 타일링 (07.25)

문제

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

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

 

접근법

dp문제의 가장 기본이 되는 문제이다.

점화식은 dp[n] = dp[n-1] + dp[n-2]로 도출할 수 있었다.

n-1이 되는 경우는 1x2 타일이 하나 들어갈 경우,

n-2가 되는 경우는 2x1 타일이 위아래로 두개 들어간 경우가 해당된다.

n-2일때 1x2타일이 좌우로 두개 들어가는 가능성을 생각할 수도 있는데 

이 가능성은 이미 n-1에서 1x2타일이 하나 들어간 경우를 생각했으므로 중복된다.

bottomUp 방식과 topDown 방식 두 가지로 풀어보았다.

 

코드

class Solution {
	private int[] dp;
    public int solution(int n) {
        dp = new int[n+1];
        return topDown(n);

    }

    public int bottomUp(int n){

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

    public int topDown(int n){
        if(n == 1) {
            dp[n] = 1;
            return 1;
        }
        if(n == 2) {
            dp[n] = 2;
            return 2;
        }
        if(dp[n] > 0)
            return dp[n];

        dp[n] = (topDown(n-1) + topDown(n-2)) % 1000000007;

        return dp[n];
    }
}