[알고리즘 16.1.6] 동적계획법 - 직사각형 배치의 경우의 수

문제

---

2 x N 직사각형 모양의 칸이 있다. 이를 2 x 1 모양의 타일로 가득 채우려 한다. 가능한 경우의 수를 출력하는 프로그램을 작성하시오. 단, 가능한 경우의 수가 매우 많을 수 있으므로, 그 경우의 수를 1,000,007 로 나눈 나머지를 출력한다.

예를 들어, N = 3 일 경우에는 다음 세 가지의 가능한 경우가 존재한다.

 

입력

---

첫 번째 줄에 N이 주어진다. ( 1 ≤ N ≤ 100 )  

출력

---

가능한 경우의 수를 1,000,007 로 나눈 나머지를 출력한다.

 

예제 입력

3

예제 출력

3

 

예제 입력

8

예제 출력

34

 

예제 입력

37

예제 출력

87896

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

#include<iostream>
 
using namespace std;
 
const int MAX = 105;
int n;
int t[MAX]={0,};
 
 
int main(){
  
  cin>>n;
  
  t[0] = 0;
  t[1] = 1;
  t[2] = 2;
  
  for(int i=3; i<=n; i++){
    t[i] = t[i-2] + t[i-1];
    t[i] %= 1000007;
  }
  
  cout<<t[n]<<endl;
  
  return 0;
}