(DP)

사실 DP의 관건은 하위 문제의 구조를 찾는 데 있다.우리는arr[i][j]를 j 왼쪽에 i를 기입할 때의 개수로 규정하는데 뚜렷하다:arr[i][j]=a[0][i]+a[1][i]+...+rr[i/2][i](i<=j/2) 우리는 먼저 arr[0][t]=1(0<=t<=n, n은 입력의 자연수)를 규정한다. 왜냐하면 왼쪽에 0을 채울 때 이 수이고 수의 개수는 당연히 1이기 때문이다. 
자문제의 구조에 따라 먼저 자문제를 풀고 다시 원문제의 해를 얻다. 
 

/*

 * zy_1009.cpp

 *

 *  Created on: 2013 12 15 

 *      Author: Administrator

 */





#include <iostream>



using namespace std;



const int maxn = 1005;





int a[maxn][maxn];

int n;



void prepare(){

//	memset(a,0,sizeof(a));





	int i,j;



	for(i = 0 ; i <= 500 ; ++i){

		for(j = 0 ; j <= 1000 ; ++j){

			a[i][j] = 0;

		}

	}

	for(i = 1 ; i < maxn ; ++i){

		a[0][i] = 1;

	}



	int k;

	for(i = 0 ; i <= n ; ++i){

		for(j = 1 ; j <= i/2 ; ++j){

			for(k = 0 ; k < j ; ++k){

				a[j][i] += a[k][j];

			}

		}

	}

}

int main(){





	while(scanf("%d",&n)!=EOF){

		prepare();



		int sum = 0;



		int i;

		for(i = 0 ; i <= n/2 ; ++i){

			sum += a[i][n];

		}



//		printf("%d
",sum);

		cout<<sum<<endl;

	}



	return 0;

}