JAVA) 11726번 2*n 타일링 - 다이나믹 프로그래밍

1. Top-Down 방식

import java.util.Scanner;

public class Main {
    static int[] memo;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        memo = new int[n+1];
        memo[0] = 1;
        memo[1] = 1;
        System.out.println(tiling(n));
    }

    public static int tiling(int num) {
        // Top-Down 방식
        // A[n] = 2*n 직사각형을 타일로 채우는 방법의 수
        // 점화식 : A[n] = A[n-1] + A[n-2] (세로로 하나 놓았을 때 + 가로로 2개 놓았을 때)
        if (num < 2) { // 예외처리
            return memo[num];
        }
        if (memo[num-1] == 0) { // 푼 적 없는 부분 문제의 경우
            memo[num-1] = tiling(num-1);
        }
        if (memo[num-2] == 0) { // 푼 적 없는 부분 문제의 경우
            memo[num-2] = tiling(num-2);
        }
        memo[num] = memo[num-1] + memo[num-2];
        memo[num] %= 10007;
        return memo[num];
    }
}

 

2. Bottom-Up 방식

import java.util.Scanner;

public class Main {
    static int[] memo;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        memo = new int[n+1];
        memo[0] = 1;
        memo[1] = 1;
        System.out.println(tiling(n));
    }

    public static int tiling(int num) {
        // Bottom-Up 방식
        // A[n] = 2*n 직사각형을 타일로 채우는 방법의 수
        // 점화식 : A[n] = A[n-1] + A[n-2] (세로로 하나 놓았을 때 + 가로로 2개 놓았을 때)
        if (num < 2) {
            return memo[num];
        }
        for (int i=2;i<num+1;i++) {
            memo[i] = memo[i-1] + memo[i-2];
            memo[i] %= 10007;
        }
        return memo[num];
    }
}