[Programmers] Level2 : 3 X n 타일링

Question

---

Solution

• 완성된 직사각형 n에 대하여 가로길이를 2만큼 잘랐을때 만들 수 있는 직사각형은 3가지로 3f(n-2) 가 나온다.
• 가로길이가 4부터는 전혀 다른 모양이 두개씩 추가 된다.
  n이 6이라면, 2f(6-4) + 2f(4-4)로 f(0)이 될때까지 계속 더해준다.
• 경우의 수가 굉장히 많기 때문에 dp를 이용하여야 한다.

---

Cord

#include <string>
#include <vector>

using namespace std;

long long dp[5001];

long long tiling(int n)
{
    // 홀수는 직사각형 불가
    // n > 2 부터 시작
    if (n == 0) { return 1; }   // 짝수의 f(0)에 대한 연산
    else if (n == 2) { return 3; }
    else if (n % 2 != 0) { return 0; }

    if (dp[n] != 0) { return dp[n]; }

    long long sum = 3 * tiling(n - 2); // 3f(n-2)
    // 짝수일 경우 특수한 두 가지에 대한 처리
    for (int i = 4; i <= n; i += 2)
    {
        sum += 2 * tiling(n - i);
    }

    return dp[n] = sum % 1000000007;
}

int solution(int n)
{
    long long answer = tiling(n);
    return answer;
}

---

Result