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

문제 링크 : programmers.co.kr/learn/courses/30/lessons/12902

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

세로길이는 3으로 고정이므로 가로길이가 2일 때 경우의 수는 3가지

 

가로 길이 2가 추가될 때

 

A : 전 단계의 경우의 수 x 3

 

B : 위 그림과 같이 짝수 지점을 직사각형이 끼고 있을 때 2가지 경우의 수

 

A와 B를 생각하면서 수식을 만들어보면

 

가로 길이 0일 때(d[0]) : 1 이라고 가정하자

가로 길이 2일 때(d[2]) : 3 x d[2 - 2] + 2 x 0

가로 길이 4일 때(d[4]) : 3 x d[4 - 2] + 2 x d[2 - 2]

가로 길이 6일 때(d[6]) : 3 x d[6 - 2] + 2 x d[4 - 2]

                     ......

 

가로 길이 n일 때(d[n]) : 3 x d[n - 2] + 2 x d[n - 2 - 2]

 

#include <string>
#include <vector>
#include <string.h>
using namespace std;

long long cache[5001];
const int MOD_NUMBER = 1000000007;

long long tiling(int num)
{
    long long& returnValue = cache[num];

    if(returnValue != 0){ return returnValue; }
    
    // 가로 길이가 2 늘어날때 마다 경우의 수가 3배 생기고
    returnValue += 3 * tiling(num - 2);

    // 짝수 지점마다 위쪽, 아래쪽 두가지 경우가 생김
    for(int index = 4; index <= num; index += 2)
    {
        returnValue += 2 * tiling(num - index);
    }

    returnValue %= MOD_NUMBER;

    return returnValue;
}

int solution(int n) {
    memset(cache, 0, sizeof(cache));
    cache[0] = 1; cache[2] = 3;
    int answer = tiling(n);
    return answer;
}