[Programmers] 3 x n 타일링

https://school.programmers.co.kr/learn/courses/30/lessons/12902

프로그래머스

문제 설명

2 x n 타일링 문제를 풀고 같은 유형이라고 판단된 3 x n 타일링 문제를 풀어보았다. 규칙을 간단히 찾을 줄 알았으나 쉽지 않았고 규칙을 찾기 위해 직접 세보려고 했으나 n이 6인 경우부터 엄청나게 많은 경우의 수가 나오는 것을 알게 됐고 다른 설명글을 참고하게 되었다. 규칙은 f(n)= f(n-2)*4 - f(n-4) 이다. 그리고 이 규칙을 사용하기 위해서는 모듈러 분배법칙을 알고 있어야 한다. 수가 엄청나게 커지기 때문에 이를 모듈러 연산을 통해 줄여야 한다.

• (A + B) % M = ((A % M) + (B % M)) % M
• (A * B) % M = ((A % M) * (B % M)) % M
• (A - B) % M = ((A % M) - (B % M)) % M

규칙과 모듈러 연산을 알았으므로 코드로 작성하자.

코드

class Solution {
    public int solution(int n) {
        long[] d = new long[n + 1];
        int mod = 1_000_000_007;
        
        d[2] = 3;
        d[4] = 11;
        
        for (int i = 6; i <= n; i += 2) {
            d[i] = (d[i - 2] * 4 % mod - d[i - 4] % mod + mod) % mod;
        }
        
        return (int) d[n];
    }
}