Programmers[12902] - 3 x n 타일링[Level4]

링크

프로그래머스

문제설명

• 점화식, DP

문제풀이

• DP

  • 2의 배수인 경우만 가능

  • 제일 오른쪽 배치의 경우의 수가 3가지가 있다

    • 

  • 편의상 각각 ↑↓≡으로 표시한다.

  • A_2

    • 위의 3가지경우

  • A_4

    • A_2*3 + Alpha가 있다

    • Alpha는 다음 2가지 경우가 있다

    • 

      에서 파생되는

      
    • 

      에서 파생되는

      

    • 파생되는 Alpha는 ↑↓에서 파생되는 것을 알 수 있다.

    • A_2, A_4, A_6을 트리 형식으로 표현해보면

    •  

    •  

      

    • A_4 = A_2 * 3 + Alpha([주황](1 * 2))

    • A_6 = A_4 * 3 + Alpha([주황](1 * 2) + [파랑](A_2 * 2))

    • A_8 = A_6 * 3 + Alpha([주황](1 * 2) + [파랑](A_4 * 2) + [초록](A_6 * 2))

    • 이렇게 점화식이 진행되는 것을 알 수 있다.

    • Alpha는 이전단계에서 * 2를 해서 더해주는 이유는 오른쪽 끝 모양이 ↑↓여야 추가로 모양을 만들 수 있기 때문이다.

    • 문제풀이에서는 임의로 A_0를 1로 지정했음

문제코드

public class Solution {

    public static int solution(int n) {
        int div = 1000000007;
        int l = Math.max(6, n);
        long[] dp = new long[l+1];
        long alpha = 0;
        dp[0]=1;
        dp[2]=3;
//        dp[4]=11;
//        dp[6]=41;

        for (int i = 4; i <= n; i = i+2) {
            alpha += (dp[i-4] * 2)%div;
            dp[i] = (dp[i-2]*3 + alpha)%div;
        }

        return (int)dp[n];
    }

    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            System.out.println(i+":"+solution(i));
        }
        System.out.println(solution(5000));
    }
}

아쉬운점

• 점화식을 제대로 못찾았었음.
  • 이전항이 어떻게 참조되는지 잘 생각해봐야 함.
  • 추가로 더해주는 항이 이전항들의 합이란 생각을 못했었음.
• div 해줘도 범위초과날 수 있으므로 long형 사용해야함

잘한점

• 이렇게 트리형식으로 그려보면서 점화식을 찾으면 이전의 항이 어디서 참조되는지 눈으로 볼 수 있음.
• DP로 구했음.