[Programmers / Level 2] 12900. 2xn 타일링 (Java)

💡 Info

• 난이도: Lv2
  프로그래머스 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12900
  풀이 링크(GitHub): hayannn/CodingTest_Java/프로그래머스/2/2xn 타일링

입출력 조건

입출력 예시

문제 이해

• 가로, 세로 길이가 정해져 있는 사각형을 통해 직사각형을 채우는 방법의 수를 세는 문제

알고리즘

풀이 시간 : 12분

• 첫 번째 경우 : 마지막에 2×1 타일 하나를 세로로 배치
  • 2×(n-1) 크기를 채우는 경우의 수
• 두 번째 경우 : 마지막에 1×2 타일 두 개를 가로로 배치
  • 2×(n-2) 크기를 채우는 경우의 수
• 점화식 : dp[n] = dp[n-1] + dp[n-2] 사용

class Solution {
    public int solution(int n) {
        int[] dp = new int[n + 1];

        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
        }
        
        return dp[n];
    }
}

결과

✍️ 다른 풀이 - 행렬 거듭제곱 이용

• 점화식을 행렬로 변환 : 피보나치와 동일한 구조 활용
• 분할정복 거듭제곱 : 지수를 절반씩 줄여가며 계산
• 행렬 곱셈 : 2×2 행렬 곱셈 직접 구현
• 모듈러 연산 : 각 단계에서 오버플로우 방지

class Solution {
    private static final int MOD = 1000000007;
    
    public int solution(int n) {
        // 기저 사례
        if (n == 1) return 1;
        if (n == 2) return 2;
        
        // 행렬 거듭제곱: [[1,1],[1,0]]^n
        long[][] result = matrixPower(new long[][]{{1, 1}, {1, 0}}, n);
        
        // T(n) = F(n+1) = result[0][0]
        return (int)(result[0][0] % MOD);
    }
    
    private long[][] matrixPower(long[][] matrix, int power) {
        if (power == 1) {
            return copyMatrix(matrix);
        }
        
        if (power % 2 == 0) {
            long[][] half = matrixPower(matrix, power / 2);
            return multiplyMatrix(half, half);
        } else {
            return multiplyMatrix(matrix, matrixPower(matrix, power - 1));
        }
    }
    
    private long[][] multiplyMatrix(long[][] a, long[][] b) {
        long[][] result = new long[2][2];
        
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 2; k++) {
                    result[i][j] = (result[i][j] + a[i][k] * b[k][j]) % MOD;
                }
            }
        }
        
        return result;
    }
    
    private long[][] copyMatrix(long[][] matrix) {
        long[][] copy = new long[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                copy[i][j] = matrix[i][j];
            }
        }
        return copy;
    }
}