[실전 문제] 직사각형배치의경우의수

1. 문제

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

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

---

입력

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

출력

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

예제 입력

case 1) 3

case 2) 8

case 3) 37

예제 출력

case 1) 3

case 2) 34

case 3) 87896

 

 

 

2. 풀이

전형적인 피보나치 수열 문제이다.

import java.io.*;

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    public static void main(String[] args) throws IOException {

        int n = Integer.parseInt(br.readLine());
        
        // Bottom-Up
        int[] arr = new int[105];

        arr[1] = 1;
        arr[2] = 2;
        arr[3] = 3;

        for (int i = 4; i <= n; i++) {
            arr[i] = (arr[i - 1] + arr[i - 2]) % 1000007;
        }
        bw.write(arr[n] + "");
        
        br.close();
        bw.flush();
        bw.close();
    }

    /*
    // Top-Down 방식
    private static int squareBatch(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1; // n = 1일 때
        if(n == 2) return 2; // n = 2일 때
        if(n == 3) return 3; // n = 3일 때

        return (squareBatch(n-1) + squareBatch(n-2)) % 1000007;
    }

     */

}