직사각형배치경우의수

dp문제 

2*n 직사각형을 채우는 경우의 수는

끝에 타일이 '|' 인 경우와 '='인 경우 두가지 경우수를 합하는 것과 같다.    

import java.util.Scanner;
public class Main{
    // 입력 1~100(n)
    // 출력 가능한 경우를 1000007로 나눈 나머지
    // 이해: 2*n 사각형을 2*n으로 채우는 것
    public static int[] arr = new int[120];
    public static void main(String[] args){

      arr[2]=2;
      arr[3]=3;
      Scanner scan = new Scanner(System.in);
    
      int n = scan.nextInt();
      if(n==1){System.out.println(1);return;}
      if(n==2){System.out.println(2);return;}
      if(n==3){System.out.println(3);return;}
      for(int i=4;i<=n;i++)
      {
        arr[i]=(arr[i-1]+arr[i-2])%1000007;
      }
      System.out.println(arr[n]);
    }
}