백준 11726번 2Xn타일링 (JAVA)

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

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

일단 전화식은 f(n) = f(n-1) + f(n-2)로 구하였습니다.

n번째 칸에 세로로 2인 직사각형을 넣으면 f(n-1)값이 되고, 가로로 2인 직사각형 2개를 넣으면 f(n-2)값이 되기 때문입니다.

이 값을 DP에 저장하며 문제를 해결하였습니다. 

 

package BOJ.dp;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BOJ_11726 {
    private static final int NOT_VALID = -1;
    private static final int LIMIT = 10_007;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[1001];
        Arrays.fill(dp,NOT_VALID);
        dp[1] = 1;
        dp[2] = 2;
        int result = cal(n,dp);
        System.out.println(result);
    }

    private static int cal(int n, int[]dp) {
        if(dp[n] != NOT_VALID){
            return dp[n];
        }
        return dp[n] = (cal(n-1,dp) + cal(n-2,dp))% LIMIT;
    }
}