직사각형 배치의 경우의 수

직사각형 배치의 경우의 수

 

문제

---

2 x N 직사각형 모양의 칸이 있다. 이를 2 x 1 모양의 타일로 가득 채우려 한다. 가능한 경우의 수를 출력하는 프로그램을 작성하시오. 단, 가능한 경우의 수가 매우 많을 수 있으므로, 그 경우의 수를 1,000,007 로 나눈 나머지를 출력한다.

예를 들어, N = 3 일 경우에는 다음 세 가지의 가능한 경우가 존재한다.

 

입력

---

첫 번째 줄에 N이 주어진다. ( 1 ≤ N ≤ 100 )  

출력

---

가능한 경우의 수를 1,000,007 로 나눈 나머지를 출력한다.

 

예제 입력

3

예제 출력

3

 

예제 입력

8

예제 출력

34

 

예제 입력

37

예제 출력

87896

코드

///사각형

import java.util.*;

public class Main {

//    public static ArrayList<Integer> box = new ArrayList<>();
    public static int result = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //총 몇개의 숫자를 입력 받을 것인지
        int a;
        int b[][];
        int d[];
        int count = 0;
        long max = Integer.MIN_VALUE;
        a = sc.nextInt();

        d = new int[a+1];

        for(int i = 1 ; i <= a; i++){
            if(i < 3) d[i] = i;
            else d[i] = (d[i-1] + d[i-2])%1000007;
        }

        System.out.println(d[a]);

        sc.close();

    }

}