코영방

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

전형적인 다이내믹 (동적계획법)문제다.

점화식은 아래 스케치를 참고하세요.^^

점화식 : K(n) = K(n-1) + 2*K(n-2)

<Top-Down - 재귀함수 사용 방법>

#include<bits/stdc++.h>
using namespace std;

int d[1001];

int tile(int n)
{
    if(n < 2) return 1;
    if(d[n] > 0) return d[n];
    
    d[n] = (tile(n-1) + tile(n-2) + tile(n-2))%10007;
    return d[n];
}
int main() {

    int n;
    scanf("%d",&n);

    printf("%d\n",tile(n));
    return 0;
}

<Bottom-Up>

#include<stdio.h>
int k[1004];
int main()
{
	int n,i,j;
	scanf("%d",&n);
	for(i=1; i<=1004; i++)k[i]=0;
	k[1]=1;
	k[2]=3;
	for(i=3; i<=n; i++){
        k[i]=k[i-1]+k[i-2]*2;
	}
	printf("%d",k[n]%10007);
	return 0;
}