[7] [Class 3] - 백준 11727 2xn 타일링 2

www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

 

딱 보면 알지만 단순한 동적 프로그래밍 문제입니다.

점화식을 세워서 문제를 해결해야하는데, 점화식 세우는게 어찌 이리 어려운지..

따로 문제들 풀면서 연습을 해봐야할 것 같습니다. 

 

#include <bits/stdc++.h>

using namespace std;

long long dp[1001];

int main(){
  ios_base :: sync_with_stdio(false); 
  cin.tie(NULL);

  int N;
  cin >> N;

  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] % 10007;

  return 0;
}