알고리즘/Array

2×n 타일링

e-pd 2021. 7. 13. 20:04

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

 

11726번: 2×n 타일링

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

www.acmicpc.net

 

public class Problem11726 {
    private static int MOD_NUMBER = 10007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        System.out.println(solve(n));
    }

    private static int solve(int n) {
        int[] tiles = new int[n+1];

        for (int i = 0; i <= n; i++) {
            tiles[i] = getTiles(i, tiles) % MOD_NUMBER;
        }

        return tiles[n];
    }

    private static int getTiles(int n, int[] tiles) {
        if (n <= 2) {
            return n;
        } else {
            return tiles[(n-1) + tiles[(n-2)]];
        }
    }
}