BOJ 2718 타일 채우기

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

문제

4N 크기의 타일을 21, 12 크기의 도미노로 완전히 채우려고 한다. 예를 들어 42 타일을 채우는 방법은 다음과 같이 5가지가 있다.

N이 주어졌을 때, 타일을 채우는 방법의 개수를 출력하는 프로그램을 작성하시오.

---

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 1,000보다 작거나 같은 자연수이다. 각 테스트 케이스는 정수 하나로 이루어져 있다. 이 정수는 문제에서 설명한 타일의 너비 N이다. N은 자연수이다.

N은 타일을 채우는 경우의 수가 2,147,483,647 이하이도록 주어진다.

---

출력

각 테스트 케이스에 대해 4*N크기의 타일을 채우는 방법의 경우의 수를 출력한다.

---

예제 입력 1

3
2
3
7

예제 출력 1

5
11
781

---

코드

이전에 풀었던 BOJ 2133 타일 채우기와 매우 유사하게 생긴 문제여서 비슷한 방식으로 규칙성을 찾으려 했지만…

결국 찾지 못하고 다른 블로그를 참고했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int[] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine()), max = Integer.MIN_VALUE;
        int[] inputs = new int[T];
        for (int i = 0; i < T; i++) {
            inputs[i] = Integer.parseInt(br.readLine());
            max = Integer.max(max, inputs[i]);
        }

        StringBuilder answer = new StringBuilder();
        dp = new int[max + 1];
        dp[0] = dp[1] = 1;
        dp[2] = 5;
        for (int input: inputs)
            answer.append(search(input)).append('\n');

        System.out.println(answer);
    }

    static int search(int idx) {
        if(dp[idx] != 0) return dp[idx];

        dp[idx] = search(idx - 1) + 4 * search(idx - 2);

        for (int i = 3; i <= idx; i++) {
            if((i & 1) == 0) dp[idx] += search(idx - i) * 3;
            else dp[idx] += search(idx - i) * 2;
        }

        return dp[idx];
    }
}