[백준/11726] 2xn 타일링 (Java/코드)

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

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

코드 구현

코-

import java.util.*;
import java.lang.*;
import java.io.*;
 
public class Main {
    static int[] d;
     
    public static void main(String[] args) {
        // TODO Auto-generated method stub
            // your code goes here
            //정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
 
            /*2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

            아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
            첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
            
            */
        
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            //d[n] = d[n-1] + d[n-2];
            
            d = new int[n+1];
            System.out.println(go(n));
            
        }
        
        public static final int go(int n){
            if ( n == 0 ) {
                d[n] = 1;
                return d[n];
            }    if ( n == 1 ) {
                d[n] = 1;
                return d[n];
            }
            
            if ( d[n]>0 ) return d[n];
            
            d[n] = (go(n-1) + go(n-2))%10007;
            
            return d[n];
        }
            
        
    
 
}