[백준] 11727.cpp : 2 x n 타일링 2

www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

#include <iostream>

using namespace std;

int n;
int ans[1001] = {0, 1, 3,};

int main(void)
{
  cin >> n;
  for(int i = 3 ; i <= n ; i++)
  {
    // i번째 경우 = i-1번째에 2x1 놓기 + i-2번째에 x 2번(2x2 / 1x2 두개 놓기)
    ans[i]       = (ans[i-1]         + ans[i-2]  * 2)    % 10007;
  }
  cout << ans[n] << '\n';
}

 

[Try]

1. 2xn 타일링 1번 문제와 비슷한 느낌으로 접근하였다.

 

[Point]

1. 2x2 박스가 추가된 것인데, n-2 번째의 경우의 수에서 2x2 를 놓냐 2x1 을 놓냐의 두가지가 생긴 것이기 때문에 2만 곱해주면 끝!