3 x n tiling

해당 문제는 여기에서 확인하실 수 있습니다.

이 문제는 동적 계획법(DP)을 사용해 해결할 수 있는 문제입니다. 바닥의 크기가 3 x n인 상황에서 타일을 채우는 방법의 수를 구하는 것이 핵심입니다. 타일의 배치는 규칙성을 따르고, 이러한 규칙성을 점화식으로 정의할 수 있습니다. 문제를 풀기 위해서는 n의 값이 짝수일 때만 바닥을 가득 채울 수 있음을 이해해야 합니다. 홀수일 경우에는 채울 수 없으므로 이를 배제하고, 짝수의 경우에만 경우의 수를 계산합니다.

우선, n이 2인 경우의 타일 배치를 생각해보면 3가지 방법이 존재합니다. 이를 기반으로 더 큰 n에 대한 점화식을 세우게 되는데, n이 증가할 때의 경우의 수는 이전 타일 배치 방법을 기반으로 계산됩니다. 구체적으로, 길이가 n인 바닥을 채우는 경우는 길이가 n-2인 바닥을 채운 후에 타일을 추가하거나, 길이가 n-4인 바닥에서 더 복잡한 패턴으로 타일을 배치하는 방식으로 표현할 수 있습니다.

따라서, 점화식은 f(n) = f(n-2) * 4 - f(n-4) 형태로 구성됩니다. 이 점화식을 사용하면, 타일의 배치 수를 효율적으로 구할 수 있습니다. 큰 수를 다루기 때문에, 문제에서 요구한 대로 계산 과정에서 결과값을 1000000007로 나눈 나머지를 반환하도록 모듈러 연산을 적용해줍니다.

이러한 논리적 흐름을 기반으로 DP 테이블을 채워가며 최종적으로 n에 대한 답을 구할 수 있습니다.

class Solution {
  long[] tile = new long[5001];  // 타일을 채우는 경우의 수를 저장할 배열
  
  public long solution(int n) {
    int mod = 1000000007;  // 큰 수 처리를 위한 모듈러 값
    
    tile[0] = 1;  // 길이 0인 경우, 채울 수 있는 방법은 1가지
    tile[2] = 3;  // 길이 2인 경우, 채울 수 있는 방법은 3가지
    
    // 짝수 길이만 채울 수 있으므로 2씩 증가
    for (int i = 4; i <= n; i += 2) {
      // 점화식 적용: tile[i] = (tile[i-2] * 4 - tile[i-4]) % mod
      tile[i] = (tile[i-2] * 4 % mod - tile[i-4] % mod + mod) % mod;
    }
    
    return tile[n];  // 최종적으로 n 길이를 채우는 방법의 수 반환
  }
}