백준 11726번 2xn 타일링(JAVA)

문제

11726번: 2×n 타일링

 

풀이

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[1001];

        arr[1] = 1; // 2x1 크기의 직사각형을 채우는 방법은 2x1 타일로 채우는 한가지 방법 밖에 없다.
        arr[2] = 2; // 2x1 2개로 만들거나 1x2 2개로 만드는 방법이 있다.

        for (int i = 3; i <= n; i++) {
            // 2 x (n - 1) 크기의 직사각형 뒤에 2x1을 한 개 붙이는 방법 수와
            // 2 x (n - 2) 크기의 직사각형 뒤에 1x2를 두 개 붙이는 방법 수의 합으로 구해준다.
            arr[i] = (arr[i - 1] + arr[i - 2]) % 10007;
        }

        System.out.println(arr[n]);
    }
}

arr[i] = (arr[i - 1] + arr[i - 2]); 점화식을 그림으로 나타내면 위와 같다. 예를 들어 n이 3일 때는 2x2 직사각형과 2x1 직사각형으로 나누어 생각하고, 각 직사각형을 만들 수 있는 방법의 수를 더하여 구해주면 되는 간단한 로직이다.