[BOJ-11726][DP] 2×n 타일링 - Java

문제 바로가기

11726번: 2×n 타일링

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 문제입니다.

점화식을 구해보면 dp[n] = dp[n-2] + dp[n-1] 가 됩니다.. n=4 정도까지 해보니 얼추 나오는디 사실 어떻게 하면 점화식을 잘 구하는지 잘 모르겠슴다 ㅜ

//top-down

private static int topDown(int n){
        if(n == 0 || n == 1) return 1;
        if(dp[n] != 0) return dp[n];

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

        return dp[n];
}

//bottom-up

private static int bottomUp(int n){
        dp[0] = 1;
        dp[1] = 1;

        for(int i = 2; i<=n;i++){
            dp[i] = dp[i-2] + dp[i-1];
            dp[i] %= 10007;
        }

        return dp[n];
}

DP 많이 연습해보아야겠습니다....

감사함니다 ㅜ