[프로그래머스] 3 x n 타일링

문제

programmers.co.kr/learn/courses/30/lessons/12902

코딩테스트 연습 - 3 x n 타일링

문제해결방법

이 문제는 2x1 짜리 타일을 가로, 세로로 사용해서 3xn 직사각형을 채우는 문제였다.

직사각형의 세로는 3인데 세로 3을 만족하면서 직사각형을 만드는 방법은 아래 두 가지 케이스가 있다.

1. 가로가 2이고 세로가 3인 타일

2. 가로가 4 이상인 짝수들 (4, 6, 8 ... ) / 뒤집은 모양도 있다.

따라서 가로가 홀수인 경우는 타일을 채울 수 없다.

DP 배열에 가로가 n인 직사각형을 채우는 경우의 수를 저장한다고 가정했을 때 DP[n]을 구하는 방법은 아래와 같다.

DP[n] = ( DP[n-2] * 3 ) + ( DP[n-4] + DP[n-6] + ... + DP[2] + DP[0] ) * 2

* 이 문제를 풀면서 int로도 숫자 범위를 만족한다고 생각했는데 어디서 잘못했는지 계속 틀려서 long으로 풀었다

코드

package Programmers;
 
public class Solution_3xn타일링 {
 
    public static int solution(int n) {
        int answer = 0;
        if((n&1)==0) {
            n>>=1;
            long[] DP = new long[n+1];
            long[] sum = new long[n+1];
            DP[0] = 1;
            sum[0] = 1;
            for(int i=1; i<=n; i++) {
                DP[i] = (DP[i-1]*3);
                if(i>=2) DP[i] = (DP[i]+sum[i-2]*2)%1000000007;
                sum[i] = (DP[i]+sum[i-1])%1000000007;
            }
            answer = (int) DP[n];
        }
        return answer;
    }
    
    public static void main(String[] args) {
        int n = 5000;
        System.out.println(solution(n));
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.