[pro] 프로그래머스 level2 12902 3*n 타일링 (Java) - dp

[문제]

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

프로그래머스

 

[풀이]

n이 홀수이면 딱 맞는 타일링이 불가능하므로 0을 반환한다.

 

n이 2인 경우 가능한 경우의 수는 모두 3가지이다.

n이 4인 경우 n이 2인 경우를 각각 합쳐서 4를 만들 수 있으므로 f(2)*3이 된다. 또한 여기에 합치지 않고 만들 수 있는 모양이 2개가 추가로 있다. 즉 f(2)*3 + 2가 된다.

n이 6인 경우, n이 4인 경우에 n이 2인 경우를 각각 합쳐서 만들 수 있으므로 f(4)*3이 된다. 여기에 합치치 않고 만들 수 있는 모양이 역시 2개가 추가로 있으므로 f(4)*3 + 2가 된다. 또한 n이 4인 경우에 따로 만들 수 있었던 모양 2가지에 n이 2인 경우를 각각 합해줄 수 있으므로 f(2)*2가 추가된다. 즉 f(4)*3 + f(2)*2 + 2가 된다.

n이 8인 경우, n이 6인 경우에 n이 2인 경우를 각각 합쳐서 만들 수 있으므로 f(6)*3이 되고, 여기에 합치치 않고 만들 수 있는 모양이 2개가 추가로 있다. 또한 n이 6인 경우 따로 만들 수 있었던 모양 2가지에 n이 2인 경우를 각각 합해줄 수 있으므로 f(2)*2, n이 4인 경우 따로 만들 수 있던 모양 2가지에 n이 4인 경우를 각각 합해줄 수 있으므로 f(4)*2 가 추가된다. 즉 f(6)*3 + f(4)*2 + f(2)*2 + 2가 된다.

 

규칙에 맞게 dp를 채워주면 된다! 

 

참고: https://wonillism.github.io/programmers/Programmers-3xn-tiling/

 

[코드]

 

class Solution {
    public long solution(int n) {
        long answer = 0;
        if(n%2==1) return 0; //홀수면 불가능
        
        long[] dp = new long[n+1];
        dp[0] = 1;
        dp[2] = 3;
        for(int i=4; i<=n; i+=2){
            dp[i] = dp[i-2]*3;
            for(int j=i-4; j>=0; j-=2){
                dp[i] += dp[j]*2;
            }
            dp[i] %= 1000000007;
        }
        
        answer = dp[n];
        
        return answer;
    }
}