[프로그래머스 2레벨] 3 x n 타일링 (C++)

#include <string>
#include <vector>

using namespace std;

const int MOD = 1000000007;
long long dp[50001];

int solution(int n) {
    
    if(n%2==1) return 0; //홀수는 불가
    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] %= MOD;
    }
    
    return dp[n];
}

 

규칙을 통해 dp로 풀 수 있는 문제이다.

먼저 블록 특성 상 홀수 값에 대해서는 타일을 완벽히 채우는 것이 아에 불가능하므로, 이 경우 바로 0을 리턴해준다.

 

이제 짝수의 경우만 체크하자.

먼저 dp[2]의 경우를 직접 그려보면 3가지 케이스가 나오는 것을 알 수 있다.

이대로 dp[4]의 경우를 체크해보면, 가로가 2의 2배이므로, 절반씩 dp[2]의 케이스를 할당할 수 있다.

따라서 이러한 3가지 케이스로만 조합할 수 있기에, 모든 조합을 따져보면 dp[2]*3이 된다.

 

그러나 dp[4]의 경우 이러한 조합을 제외하고도 특이한 블록 형태를 가진 2가지가 존재한다.

이는 4일때부터 생겨나므로, 현재 i에서 4를 뺀 값부터 시작하여 해당 케이스가 존재하는 지 체크하여 더해줄 필요가 있다.

따라서 이를 식으로 표현하면 dp[i] += dp[j]*2가 된다.

마지막으로 주어진 조건에 따라 모듈러 계산을 해주어야 한다.