프로그래머스 [Lv. 2] 3 x n 타일링 {언어 : Java}

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12902?language=java#

프로그래머스

정답 코드

import java.util.Arrays;

class Solution {
    public long solution(int n) {
        if (n % 2 == 1) {
            return 0;
        }
        if (n == 2) {
            return 2;
        }
        if (n == 4) {
            return 11;
        }
        int range = n / 2 + 1;
        long[] dp = new long[range];
        dp[1] = 3;
        dp[2] = 11;
        for (int num = 3; num < range; num++) {
            dp[num] += dp[num-1] * 3;
            for (int prev = num-2; prev > 0; prev--) {
                dp[num] += dp[prev] * 2;
            }
            dp[num] = (dp[num] + 2) % 1000000007;
        }
        long answer = dp[n/2];
        return answer;
    }
}

풀이 방법

1. 값을 유추해본다.
   1. f(2) = 3; f(4) = 11; f(6) = 41; f(8) = 153;
   2. f(6) = f(4) * 3 + f(2) * 2 + 2; f(8) = f(6) * 3 + f(4) * 2 + f(2) * 2 + 2;
   3. f(n) = f(n-2) * 3 + f(n-1) * 2 + ... + f(2) * 2 + 2;
2. n이 홀수면 무조건 0이므로 0을 반환한다.
3. n이 짝수면 편의상 2로 나눠서 long type의 dp 배열을 만든다.
4. dp[num]에 바로 뒤의 값에 3을 곱해서 더하고 반복문을 통해 나머지 값들에 2를 곱해서 더한다.
5. 마지막으로 2를 더하고 1,000,000,007로 나누고 나머지를 저장한다.
6. range만큼 반복한다.
7. dp[n/2]를 반환하면 끝!

느낀점

• 점화식을 유추하는 것은 어렵다.