[BOJ] 11727번 : 2 x n 타일링 2

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
int n;
int d[1005]; 

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	d[1] = 1; 
	d[2] = 3;
	for (int i = 3; i <= 1000;i++) {
		d[i] = (d[i - 1] + 2 * d[i - 2]) % 10007;
	}
	cin >> n; 
	cout << d[n] << '\n';

}

 

3. solution 2 :

#include <stdio.h>

int dp[1001];

int rec(int x)
{
	if (x == 1) return 1;
	if (x == 2) return 3;

	if (dp[x] != 0)
	{
		return dp[x];
	}

	return dp[x] = ( rec(x-1) + 2 * rec(x-2) ) % 10007;
}

int main()
{
	int N;
	int ans;

	scanf("%d", &N);

	ans = rec(N);

	printf("%d\n", ans);

	return 0;
}

source code 출처 : https://www.acmicpc.net/source/83257722