백준 11726번 - 2xN 타일링

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

n이 1일 때는 1개, 2일 때는 2개, 3일 때는 3개...

위와 같은 형태로 n이 늘어날 때 규칙을 찾을 수 있다.

바로 n일 때 n-2에서 가로의 길이가 2인 사각형을 더하는 경우와 n-1에서 가로의 길이가 1, 세로가 2인 경우를 더해주는 것이다. 

n-1과 n-2에 붙여주는 사각형은 가로의 길이가 다르기 때문에 중복은 없다.

그리고 문제의 조건에서 결과값에 10007을 나눈 값을 구하는 경우이기 때문에 숫자가 커지더라도 

int의 범위를 넘지 않기 때문에 변수의 타입은 int로 해주었다.

#include <iostream>
using namespace std;
 
int main(){
    int n;
    cin>>n;
    
    int dp[1001]={0};
    dp[1]=1, dp[2]=2;
    
    for(int i=3;i<=n;i++){
        dp[i]=(dp[i-1]+dp[i-2]);
        dp[i]%=10007;
    }
    
    cout<<dp[n]<<endl;
}