POJ 1775 Sum of Factorials (ZOJ 2358)

http://poj.org/problem?id=1775
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1334
テーマ:
数nをあげてnがいくつかの階乗の和に分解できるかどうかを見ます
9=1!2!+3!
方法1:
最初は0~10の階乗を直接打つことを考えていたが,10の階乗はnの範囲より大きくなった.
そしてDFSも、過ぎていきました.でも時間が惨め...
注意n=0出力NOと0!=1

#include<cstdio>
#include<cstring>
const int MAXN=10;
int temp[12]={1,1};
bool used[12];
bool ok;
void dfs(int cur,int sum,int target)
{
	if(sum >target)
		return;

	if(sum==target)
	{
		ok=true;
		return ;
	}

	for(int i=cur;i<=MAXN;i++)
	{
		if(used[i]==false)
		{
			used[i]=true;
			dfs(i,sum+temp[i],target);		
			used[i]=false;
		}
	}
}
int main()
{
	
	for(int i=2;i<=MAXN;i++)
		temp[i]=temp[i-1]*i;

	int n;
	while(scanf("%d",&n),n>=0)
	{

		if(n==0)
		{
			printf("NO
");
			continue;
		}
		memset(used,0,sizeof(used));
		ok=false;
		dfs(0,0,n);

		if(ok)  
            printf("YES
");  
        else  
            printf("NO
");  
	}
	return 0;
}

方法2:
欲張る.
そしてnを超えない階乗を減算する.
n!>=sum(1 ! + 2!+……n-1!)

#include<cstdio>
const int MAXN=10;
int main()
{
	int temp[12]={1,1};
	for(int i=2;i<=MAXN;i++)
		temp[i]=temp[i-1]*i;

	int n;
	while(scanf("%d",&n),n>=0)
	{
		if(n==0)
		{
			printf("NO
");
			continue;
		}
		for(int i=MAXN;i>=0;i--)
		{
			if(n >=temp[i])
				n-=temp[i];
		}
		if(n==0)
			printf("YES
");
		else
			printf("NO
");
	}
	return 0;
}