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

🔗 문제링크

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

📂 분류

DP

💡 풀이

이 문제는 2 x n 타일링을 응용한 문제이다.

 

세로 길이가 3인 바닥이기 때문에 n이 홀수 일 경우 타일 배치를 하지못한다.

처음 점화식은 dp[i] = dp[i - 2] * 4 - dp[i - 4]로 쉽게 구해졌으나 나머지 연산에 문제가 있어서 이 점화식으로는 문제를 해결하지 못했다. 다른 점화식을 구하려고 고민을 했으나 생각이 나지않아 풀이법을 참고해서 풀었다. 점화식은 다음과 같다.

tiles[i] = tiles[i - 2] * 3 + tiles[i - 4] * 2 + tils[i - 6] * 2 ...

💻 코드

public class Solution {

    private static final int MOD = 1000000007;

    public int solution(int n) {
        long[] tiles = new long[n + 1];

        tiles[0] = 1;
        tiles[2] = 3;

        for (int i = 4; i <= n; i += 2) {
            tiles[i] = tiles[i - 2] * 3;
            for (int j = i - 4; j >= 0 ; j -= 2) {
                tiles[i] += (tiles[j] * 2);
            }
            tiles[i] %= MOD;
        }

        return (int) tiles[n];
    }
}