[AlgoSpot] 타일링 방법의 수 세기

문제 설명

알고리즘 문제 해결 전략 - 동적 계획법
https://algospot.com/judge/problem/read/TILING2

문제 풀이

• 기본적인 동적 계획법 문제이다.
• 아래와 같은 점화식을 이용하였다.

  dp(n) = dp(n - 1) + dp(n-2)

소스 코드 (JAVA)

import java.util.Scanner;

public class Main {
    public static int C, N;
    public static int MOD = 1000000007;
    public static int dp[] = new int[101];

    public static int solve(int n) {
        if (n <= 1) return 1;
        if (dp[n] != -1) return dp[n];
        int result;
        result = (solve(n - 1) + solve(n - 2)) % MOD;
        dp[n] = result;
        return result;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        C = sc.nextInt();
        for (int i = 0; i <= 100; i++) dp[i] = -1;
        for (int c = 0; c < C; c++) {
            N = sc.nextInt();
            System.out.println(solve(N));
        }
    }
}