import java.util.*;

class Solution {
    private static final int mod = 1_000_000_007;  // 결과를 나눌 모듈러 값
    
    public int solution(int n) {
        if (n % 2 != 0) return 0;  // n이 홀수일 경우, 완전히 채울 수 없음
        
        int[] dp = new int[n + 1];
        dp[0] = 1;  // 초기값: 가로 길이가 0일 때 타일을 채우는 유일한 방법
        dp[2] = 3;  // 초기값: 가로 길이가 2일 때 타일을 채우는 방법의 수
        
        // dp 점화식을 통한 타일 채우기 경우의 수 계산
        for (int i = 4; i <= n; i += 2) {
            long currCnt = 3L * dp[i - 2] % mod;  // 이전 두 칸을 채운 뒤 새로 2칸을 추가하는 경우
            
            // 모든 이전 4칸 단위로 조합하여 새로운 패턴을 추가
            for (int j = i - 4; j >= 0; j -= 2) {
                currCnt = (currCnt + 2 * dp[j] % mod) % mod;
            }
            dp[i] = (int) currCnt;
        }
        
        return dp[n];  // 가로 길이가 n일 때의 타일링 경우의 수 반환
    }
}

 Approaches

이 문제는 세로 길이가 3인 바닥을 주어진 가로 길이 만큼의 길이로 타일로 채우는 문제로, 타일을 채우는 방식이 반복적인 패턴을 형성하기 때문에 동적 계획법(Dynamic Programming)을 사용하여 해결할 수 있습니다.

이 문제는 1 x 2 크기의 타일을 사용하여 가로가 n이고 세로가 3인 바닥을 완전히 채우는 방법의 수를 찾는 문제입니다. 타일을 세로로 배치할 수도 있고, 가로로 배치할 수도 있습니다. 하지만 가로 길이가 홀수일 경우에는 타일로 바닥을 완전히 채울 수 없습니다. 3 x n 바닥을 1 x 2 타일로 채우려면 항상 짝수 개의 타일이 필요하기 때문입니다. 따라서 가로 길이 n이 짝수일 때만 타일링이 가능합니다.

이 문제를 해결하기 위해서는 타일을 배치할 수 있는 다양한 패턴을 이해하는 것이 중요합니다. 예를 들어, 가로 길이가 2인 경우에는 타일을 채울 수 있는 세 가지 기본적인 방법이 존재합니다. 이는 가장 작은 짝수 길이에 대한 타일 배치 방식이기 때문에, 이후 더 긴 바닥을 채우기 위한 기본적인 패턴이 됩니다.

또한, 가로 길이가 4 이상으로 증가할 경우, 기본적인 타일링 방식 이외에도 길이에 따른 특수한 패턴들이 나타나기 시작합니다. 가로 길이가 n일 때의 타일링 방법 수를 구하려면, n - 2 길이에서 기본 패턴을 추가하는 경우와 0에서 n - 4 길이까지의 이전 타일링 방식에 새로운 타일을 추가하여 만드는 특수 패턴들이 결합됩니다.

이를 구체적으로 살펴보면, 가로 길이가 n인 경우의 타일링 방법 수는 다음 두 부분의 합으로 구성됩니다:

기본 패턴 확장: n - 2 길이에서 기존의 타일링 방식에 3가지 타일 배치 방법을 추가한 경우를 고려합니다. 이를 통해 n - 2 길이에서의 모든 경우에 대해 새로운 타일을 추가해 n 길이의 타일링 경우의 수를 구성합니다.
특수 패턴 누적: n - 4부터 0까지의 각 길이에서 등장하는 특수한 배치 방식에 두 가지 배치 방식을 추가하여 새로운 n 길이의 타일링 경우의 수를 더해갑니다. 예를 들어, n - 4 길이에서 새롭게 나타나는 특수 패턴들은 현재 길이에서 타일을 배치하는 독특한 방식들이며, 이는 특정 길이에 대한 고유한 배치 패턴으로서 이전의 길이들에 누적되어 n 길이의 타일링 수에 반영됩니다.

길이 n에 대해 타일링 가능한 경우의 수는 다음과 같이 증가합니다:

가로 길이 ( n )	가능한 타일 패턴 수
0	`1` 👻
2	`3`
4	`11`
6	`41`
8	`153`
10	`571`
12	`2131`
14	`7953`
16	`29681`

이와 같은 기본 패턴과 특수 패턴의 조합을 통해, 가로 길이 n에서의 전체 타일링 경우의 수가 도출되며, 이러한 관계를 점화식으로 정의하여 동적 계획법을 적용할 수 있습니다.

2. 접근 방식

가로 길이가 n인 타일링 문제는 기본 패턴과 특수한 배치 패턴을 반복하여 이루어진다는 점을 활용해, 동적 계획법으로 해결할 수 있습니다.

초기 값 설정: 점화식을 구성하기 위해 길이 0과 2에 대한 기본 값을 먼저 설정합니다. 길이 0은 타일이 없는 상태로 점화식의 기준 역할을 하기 때문에 1로 설정합니다. 길이 2는 타일을 배치할 수 있는 세 가지 방식이 가능하므로 3으로 초기화합니다.
점화식 생성과 패턴 누적: 초기값을 활용하여 가로 길이 n에서의 경우의 수를 계산하기 위해, 먼저 n - 2 길이에서 기본 패턴에 새로운 타일 배치를 추가합니다. 이어서 n - 4, n - 6 등 모든 짝수 길이에서 반복되는 특수 배치 패턴을 누적하여 경우의 수를 계산합니다. 특히 특수 패턴은 길이가 증가할수록 각 짝수 길이에서 2배씩 더해지는 특징이 있습니다. 이를 기반으로 점화식을 정리하면 다음과 같습니다:

dp[0] = 1
dp[2] = 3
dp[4] = 11
dp[6] = 41
...
dp[n] = 3 * dp[n - 2] + 2 * (dp[n - 4] + dp[n - 6] + ... + dp[0]) // 점화식
// 기본 패턴: 3 * dp[n - 2]
// 특수 패턴: 2 * (dp[n - 4] + dp[n - 6] + ... + dp[0])

모듈러 연산 적용: n이 커짐에 따라 경우의 수가 매우 커질 수 있으므로, 연산 과정에서 Java의 int 범위를 초과할 가능성이 있습니다. 이를 방지하기 위해 더 큰 범위를 가지는 long 타입을 사용하여 계산하며, 중간 및 최종 결과에서는 1,000,000,007로 나눈 나머지 값을 적용해 효율적으로 결과를 유지합니다. 이러한 모듈러 연산을 통해 큰 수 연산으로 인해 발생할 수 있는 오버플로우 문제를 방지하고 안정적인 결과를 얻을 수 있습니다.

이와 같은 방식으로 가로 길이 n에 대한 타일링 경우의 수를 효율적으로 누적하여 계산할 수 있습니다.

3. 홀수 번째 처리

가로 길이가 홀수인 경우에는 타일을 채울 수 없기 때문에, 주어진 n이 홀수일 경우 바로 0을 반환하여 종료합니다. 이 조건을 통해 불필요한 계산을 방지할 수 있습니다.

Solution.java

// n이 홀수일 경우, 타일링이 불가능하므로 0을 반환
if (n % 2 != 0) return 0;

4. 점화식 초기값 설정

타일링의 경우의 수를 계산하기 위해 배열을 생성하고 초기값을 설정합니다. 길이 0의 경우는 기본 값으로 1을, 길이 2는 세 가지 타일 배치 방식으로 채울 수 있으므로 3으로 설정합니다. 이 초기값들은 이후 점화식을 통해 더 큰 길이의 경우의 수를 계산할 수 있는 기초가 됩니다. 또한, 결과가 커질 수 있으므로 모듈러 연산을 위한 값으로 1,000,000,007을 설정해줍니다.

Solution.java

int[] dp = new int[n + 1];
dp[0] = 1;  // 초기값: 가로 길이가 0일 때 타일을 채우는 유일한 방법
dp[2] = 3;  // 초기값: 가로 길이가 2일 때 타일을 채우는 방법의 수
int mod = 1_000_000_007;  // 결과를 나눌 모듈러 값

5. 점화식을 이용한 타일링 경우의 수 계산

가로 길이가 4 이상인 경우, 이전 길이에서 기본 패턴과 특수 패턴을 사용해 경우의 수를 누적해 나갑니다. 현재 길이 n에서 타일링의 경우의 수는 두 가지 요소로 나뉩니다.

먼저, n - 2 길이에서 가능한 모든 기본 패턴을 3배수로 확장하는 방법을 추가합니다. 그 후 n - 4, n - 6 등 짝수 길이에서 생성된 특수 패턴을 모두 누적하여 현재 길이의 타일링 경우의 수를 계산합니다. 이를 통해 점화식을 구현하며, 각 단계에서 long 타입과 모듈러 연산을 적용하여 큰 수를 다룰 때 발생할 수 있는 오버플로우를 방지합니다.

Solution.java

// dp 점화식을 통한 타일 채우기 경우의 수 계산
for (int i = 4; i <= n; i += 2) {
    long currCnt = 3L * dp[i - 2] % mod;  // 이전 두 칸을 채운 뒤 새로 2칸을 추가하는 경우
    
    // 모든 이전 4칸 단위로 조합하여 새로운 패턴을 추가
    for (int j = i - 4; j >= 0; j -= 2) {
        currCnt = (currCnt + 2 * dp[j] % mod) % mod;
    }
    dp[i] = (int) currCnt;
}

6. n번째 경우의 수 반환

최종적으로, 가로 길이가 n일 때의 타일링 경우의 수를 배열에서 읽어 반환합니다. 이 결과 값은 가로 길이 n의 타일링 경우의 수를 1,000,000,007로 나눈 나머지를 적용하여 반환합니다.

Solution.java

// 가로 길이가 n일 때의 타일링 경우의 수 반환
return dp[n];

이 접근 방식을 통해, 문제에서 요구하는 타일링 경우의 수를 동적 계획법을 통해 효율적으로 구할 수 있습니다.

󰄉 Complexity

⏳ TC: O(N^2)
💾 SC: O(N)

이 문제는 각 길이마다 이전 모든 짝수 길이에 대한 경우의 수를 누적하여 계산하므로, n에 도달하기까지의 연산은 O(N^2)의 시간 복잡도를 갖습니다. 또한 결과를 저장하는 배열이 필요하여 공간 복잡도는 O(N)입니다.

Algorithm
Divide and Conquer