[백준] 11726: 2xn 타일링

문제

문제 풀이

다음과 같이 n=1부터 하나하나 그려가면서 규칙을 찾아나갔다.

즉, 규칙은 다음과 같다.
dp[n] = dp [n-1] + dp[n-2]

n번째 타일은 다음의 경우를 더한 경우의 수로 나타낼 수 있다.

• n-1번째 타일에 2x1타일 한개를 붙인 경우
• n-2번째 타일에 1x2타일 두개를 붙인 경우

코드

코드는 bottom-up 방식을 사용하였다.

import java.util.Scanner;

public class Main {

    static Integer[] dp;

    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();

        dp = new Integer[num+2];
        dp[0] =0;
        dp[1] = 1;
        dp[2] = 2;

        System.out.print(recur(num));
    }

    static int recur(int N){

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


}