타일링 방법의 수 세기

풀이

경우의 수를 세는 문제입니다. 경우의 수 계산하기 레시피를 참고해서 풀면 좋습니다.

완전 탐색 알고리즘

우선 완전 탐색을 이용해 모든 답을 만들면서 개수를 세어 보는 함수를 작성한 뒤, 메모이제이션을 이용해 동적 계획법 알고리즘으로 바꿔 봅시다. 재귀 호출을 할 때 부분 문제를 어떻게 나눌지 생각해야 합니다. 경우의 수 문제이므로 부분 문제들을 MECE를 따르도록 분류해야 합니다.
이 문제는 맨 왼쪽에 1개의 타일을 세로로 놓거나 맨 왼쪽에 2개의 타일을 가로로 놓기로 분류할 수 있습니다. 이 분류는 MECE를 따릅니다. 함수를 정의하면
$tiling(n)=2\times n$크기의 사각형을 타일로 덮는 방법을 반환한다.
점화식을 쓰면
$tiling(n) = tiling(n-1)+tiling(n-2)$
입니다.

메모이제이션

너무 쉽고 이전 문제에서 많이 해봤으므로 더 설명하지 않겠습니다.

시간 복잡도 분석

모든 부분 문제의 개수와 함수를 한 번 호출했을 때 생기는 부분 문제의 개수를 곱하면 $100\times 2=200$이므로 충분히 시간 안에 해결할 수 있습니다.

구현

import java.util.*;

public class Main {

    public static int n;
    public static int[] cache;
    public static int result;

    public static void input(Scanner scanner) {
        n = scanner.nextInt();
        cache = new int[n + 1];
    }

    public static void solve() {
        result = tiling(n);
    }

    public static int tiling(int width) {
        if (width <= 1) return 1;

        if (cache[width] != 0) return cache[width];

        return cache[width] = (tiling(width - 1) + tiling(width - 2)) % 1000000007;
    }

    public static void output() {
        System.out.println(result);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testCase = scanner.nextInt();
        for (int i = 0; i < testCase; i++) {
            input(scanner);
            solve();
            output();
        }
    }
}

회고

쉽다.