3 X n 타일링

---

출처 프로그래머스 - 3 x n 타일링

사용 언어 자바

문제 설명

가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 3이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다

• 타일을 가로로 배치 하는 경우
• 타일을 세로로 배치 하는 경우

직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

제한사항

• 가로의 길이 n은 5,000이하의 자연수 입니다.
• 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

입출력 예

| n | result | | — | —— | | 4 | 11 |

---

높이 2의 타일 문제를 풀어본 적이 있었다
이것은 높이 3인 타일 문제일 뿐, 크게 다를바 없었다
신경 써야 될 부분은

• 1,000,000,007로 나눈 나머지를 반환해야한다
• 홀수 단위로 늘어나지 않는다
• 길이 0, 2를 제외하면 기본 단위 경계에 타일이 가로로 놓여지는, 해당 길이만 가능한 특별한 배치 방식이 상하 반전을 포함해 2개씩 추가된다

최소 단위(가로 길이 2)에서는 3가지 방식이 가능하므로 3이 기본 단위의 경우의 수가 되겠다

한단위(길이 2)씩 늘어날 때마다
이전 단위(n - 2) 모든 경우의 수에 기본 단위(3)를 곱하면,

이전 단위에 최소 단위가 추가된 모든 경우의 수를 알 수 있다
추가로 이전의 특별한 배치 방식들이 섞인 경우의 수까지 더해주고
마지막으로 자신의 특별한 배치방식 2가지를 더해주면 된다

이전의 특별한 배치 방식들을 구하는 방법은 복잡할거 없다
간단하게 지금까지의 경우의 수 계산 방식이 한겹 더 있다고 보면 된다
다만 기본 단위의 경우의 수가 2일 뿐이다

구현은 이전 값을 저장할 배열을 하나 추가해서
특별한 배치 방식들의 값들을 따로 저장했다

기존의 높이 2의 타일 알고리즘에서 한겹 추가된것 뿐

지금은 이해가 됐으니까 쉽게 말하지만
사실 과정은 짧지 않았다
경우의 수가 2차원으로 늘어나는 방식을 이해하지 못했을 때는
중복값이나 추가값을 놓쳐서 많은 실패를 경험했다
몇 번이고 다시 그리고 공통된 식을 찾아내고 나서야 통과했다
수학적 센스가 있었다면 좀 더 쉬웠겠지만
부족하다고 아쉬울거 없다 많은 경험이 센스에 준한다고 믿는다

제출 답안

class Solution {
    private final long MOD = 1_000_000_007L;
    private long[][] dp = new long[2][5001];
    
    public int solution(int n) {
        dp[0][0] = 1L;
        dp[0][1] = 0;
        dp[0][2] = 3L;
        return (int) nTiling(n);
    }
    
    private long nTiling(int n) {
        if (dp[0][n] != 0) return dp[0][n];
        
        dp[0][n] = nTiling(n - 2) * 3;
        dp[1][n] = nTiling(n - 4) * 2 + dp[1][n - 2];
        dp[0][n] += dp[1][n];
        dp[0][n] %= MOD;
        return dp[0][n];
    }
}