[C++] BOJ 11726번 2*N 타일링 2

문제 출처

백준 온라인 저지

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

11727번: 2×n 타일링 2

 

문제 

 

문제 입 / 출력

 

풀이

DP를 활용해서 푼다

• 직사각형이 n-1 까지 덮여 있으면, 2x1 타일 하나를 놓을 수 있다.
• 직사각형이 n-2 까지 덮여 있으면, 1x2 타일 2개 혹은 2x2개 타일 1개를 놓을 수 있다.

위를 토대로 점화식을 세우면

$$ {a_{i}}^{} = {a_{i-1}}^{} + {a_{i-2}}^{} \times 2 $$

와 같은 결과를 얻을 수 있다.

 

코드

#include <iostream>

using namespace std;

int main() {
  int n;

  cin >> n;

  int dp[1001] = {
      0,
  };

  dp[1] = 1;
  dp[2] = 3;
  for (int i = 3; i <= n; i++) {
    dp[i] = (dp[i - 1] + dp[i - 2] * 2) % 10007;
  }
  cout << dp[n] << "\n";
}