[AlgoSpot] 비대칭 타일링

문제 설명

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

문제 풀이

• 동적 계획법 문제이다.
• 메모이제이션을 이용하여 최적화가 필요하다
• 아래와 같은 점화식과 생각을 이용하여 풀이하였다.

비대칭 타일링 갯수 = 총 타일링 갯수 - 대칭 타일링 갯수

tiling(n) = tiling(n-1) - tiling(n-2) : 총 타일링
etiling(n) = etiling(n-2) - etiling(n-4) : 대칭 타일링

소스 코드 (JAVA)

import java.util.Scanner;

public class Main {
    public static int MAX_N = 101;
    public static int MOD = 1000000007;
    public static int C, N;
    public static int tiling[];
    public static int atiling[];
    
    public static int dp_tiling(int n) {
        if (n == 0 || n == 1) return 1;
        if (tiling[n] != -1) return tiling[n];
        tiling[n] = (dp_tiling(n - 1) + dp_tiling(n - 2)) % MOD;
        return tiling[n];
    }

    public static int dp_atiling(int n) {
        if (n == 0 || n == 1 || n == 3) return 1;
        if (n == 2) return 2;
        if (atiling[n] != -1) return atiling[n];
        atiling[n] = (dp_atiling(n - 2) + dp_atiling(n - 4)) % MOD;
        return atiling[n];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        C = sc.nextInt();
        tiling = new int[MAX_N];
        atiling = new int[MAX_N];
        for (int i = 0; i < MAX_N; i++) {
            atiling[i] = -1;
            tiling[i] = -1;
        }
        for (int c = 0; c < C; c++) {
            N = sc.nextInt();
            System.out.println((dp_tiling(N) - dp_atiling(N) + MOD) % MOD);
        }
    }
}