[C++] 백준 14852번 타일 채우기 3

다이나믹 프로그래밍 문제입니다.

1. 2*1의 경우 2가지 경우가 가능합니다.
1-1. 2*1 타일 1개
1-2. 1*1 타일 2개

2*2의 경우 3가지 경우가 가능합니다.
2-1. 1*2 타일 2개
2-2. 1*2 타일 1개(위), 1*1 타일 2개 (아래)
2-3. 1*2 타일 2개(아래), 1*1 타일 2개 (위)

이를 통해 점화식을 세울수 있습니다.

DP[i] = DP[i-1] * 2 + DP[i-2] * 3

여기서 예외인 부분이 존재합니다.
3. 2*3의 경우

3-1.  ㅁㅁ-
        -ㅁㅁ

3-2.  -ㅁㅁ
      ㅁㅁ-

(ㅁㅁ 1*2 타일)
( - 1*1 타일)

위와 같은 모양이 가능합니다.
해당 모양은 2*4, 2*5 ... 2*n 모두 가능한 모양입니다.

그래서 DP를 2차원 배열로 만들어서 2번째 부분에는 위의 값을 계산하도록 하였습니다.
위의 모양은 3개이상의 공간이 있을 때 가능하므로
(3칸 전의 경우의 수 + 1칸 전의 (3.) 경우의 수) * 2 로 계산할 수 있습니다.

점화식으로 나타내면 다음과 같습니다.

DP[i][1] = (DP[i-1][1] + DP[i-3][0]) * 2

 

#include <iostream>
#define MOD 1000000007
typedef long long ll;
using namespace std;

ll DP[1000001][2];

void solution()
{
  int n;

  cin >> n;

  DP[0][0] = 0;
  DP[1][0] = 2;
  DP[2][0] = 7;
  DP[2][1] = 1;

  for (int i = 3; i <= n; ++i)
  {
    DP[i][1] = (DP[i - 3][0] + DP[i - 1][1]) % MOD;
    DP[i][0] = (DP[i][1] * 2 + DP[i - 1][0] * 2 + DP[i - 2][0] * 3) % MOD;
  }

  cout << DP[n][0] << endl;
}

int main(int argc, char *argv[])
{
  solution();

  return 0;
}