11727번 : 2xn 타일링 2

문제는 다음과 같습니다.

https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

풀이 코드는 다음과 같습니다.

#include <iostream>
using namespace std;

int main()
{
  int arr[1001]={0};
  arr[1]=1;
  arr[2]=3;
  int n;
  cin>>n;
  for(int i{3};i<=n;i++)
    {
      arr[i]=(arr[i-1]+2*arr[i-2])%10007;
    }
  cout<<arr[n];
  return 0;
}

기존 문제의 (1x2,2x1 타일만 사용) 점화식은

i개의 타일 경우의 수 = i-1개 타일 경우의 수 + i-2개 타일 경우의 수 이지만

2x2 타일이 추가됨으로 변화가 생기게 됩니다.

i-1개 타일에서 2x2 타일을 끼우는 경우의 수는 없지만 i-2개 타일에서 남은 2개의 칸을 채우는 경우의 수가 2x1또는 1x2 타일을 2개 넣는 경우 또는 2x2 타일 1개 끼워넣는 경우로 늘어났습니다.

따라서 타일 2개의 경우의 수도 기존 2에서 3으로 증가하고 점화식도

arr[i] = arr[i-1]+2*arr[i-2]로, [i-2]의 경우를 2배로 증가시켜주어야 합니다.