[11726]2 x n 타일링

문제

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

풀이

피보나치 수열과 같다.

bottom-up 방식으로 푸니까 런타임에러가 뜬다.

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] d = new int[1000+1];
        d[1] = 1;
        d[2] = 2;
        for(int i=3;i<=n;i++) {
            d[i] = (d[i-1] + d[i-2])%10007;
        }
        System.out.println(d[n]);
        scan.close();
    }
}

그래서 top-down방식으로 풀어봄

import java.util.Scanner;
 
public class Main {
 
    static int[] d = new int[1000+1];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        System.out.println(f(n));
        scan.close();
        
    }
    public static int f(int n) {
        if(n<2) return d[n] = 1;
        if(d[n]>0) {
            return d[n];
        }else {
            d[n] = (f(n-1) + f(n-2))%10007;
            return d[n];
        }
    }
}