2Xn 타일링 #11726 c++ 풀이

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

11726번: 2×n 타일링

n=1 일때 경우의 수 1

n=2 일때 경우의 수 2

n=3 일때 경우의 수 3

n=4 일때 경우의 수 5

 

여기서 피보나치같은 느낌이어서 그렇게 풀었다.

#include<iostream>

using namespace std;
int n; 
int dp[10001];
int main() {
	cin >> n;

	dp[0] = 0;
	dp[1] = 1;
	dp[2] = 2;
	
	for (int i = 3; i <= n; i++) {
		dp[i] = (dp[i - 1] + dp[i - 2])%10007 ; //다만 수가 너무 커지기 때문에 괄호로 묶어서 계속 나머지 연산을 해주어야한다. 이부분이 문제의 핵심이다.
		
	}

	cout << dp[n];
	
	return 0;
}