[알고리즘_dp] 백준, 2*N 타일링 11726번

bottom-up 방식

import java.util.Scanner;

public class backjoon_11726 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] d = new int[n+1];

        d[0] = d[1] = 1;

        for(int i=2; i<=n; i++){
            d[i] = d[i-1] + d[i-2];
            d[i] %= 10007;
        }

        System.out.println(d[n]);
    }
}

 

 

Top-down 방식

package dp;

import java.util.Scanner;

//top-down
public class backjoon_11726 {
    static int[] d = null;
    public static int tiling(int n){
        if(d[n] > 0){
            return d[n];
        }

        if(n==0 || n==1){
            return 1;
        }

        d[n] = tiling(n-1) + tiling(n-2);
        d[n] %= 10007;

        return d[n];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        d = new int[n+1];

        System.out.println(tiling(n));

    }
}