3xn 타일링 - Level4

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

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

#include <string>
#include <vector>
#include <cstring>
#define MODULER 1000000007;
using namespace std;

int solution(int n) {
    int answer = 0;
    
    long long dp[5001];
    

    if(n%2==1){return 0;}
    
    memset(dp,0,sizeof(dp));

    dp[0]=1;
    dp[2]=3;
   
    //점화식 이용
    //F[N] = F[N - 2] * F[2] + F[N - 4] * 2 + F[N - 6] * 2 + ... + F[2] * 2 + 2

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

    answer = dp[n];
    
    
    return (int)answer;
}

- 규칙성을 파악하고 점화식으로 문제를 풀어야한다. 

- yabmoons.tistory.com/471

[ 프로그래머스 3xn 타일링 (Lv4) ] (C++)

-풀이는 위의 블로그를 참고했습니다.