hdu 1466 직선의 교점수 계산 (수학)

클릭하여 링크 열기
n개의 직선의 각 교점수를 구하다
n개의 선은 교차하는 두 가지 유형으로 나눌 수 있습니다.
i개의 평행선, n-i개의 비평행선;그래서 교점의 개수 j=i*(n-i)+dp[n-i][k];여기 dp[i][j]는 i개의 직선에 j개의 교점이 있음을 나타낸다.그래서 k의 수치는 0~(i-1)*i/2;i*(n-i)는 평행선과 비평행선의 교점수이고 dp[i][j]는 비평행선 내부의 각종 교점수이다

#include"stdio.h"
#include"string.h"
int dp[22][201];
void fun()
{
	int i,k,j;
	memset(dp,0,sizeof(dp));
	dp[0][0]=1;
	dp[1][0]=1;
	dp[2][0]=1;
	dp[2][1]=1;
	
	for(i=3;i<=21;i++)
	{
		for(k=i-1;k>=0;k--)
			
			for(j=0;j<=k*(k-1)/2;j++)
				
				if(dp[k][j]==1)
					dp[i][(i-k)*k+j]=1;
				
	}
}
int main()
{
	
	int i,n;
	fun();
	while(scanf("%d",&n)!=EOF&&n)
	{
		printf("0");
		for(i=1;i<=n*(n-1)/2;i++)
		{
			if(dp[n][i]==1)
				printf(" %d",i);
		}
		printf("
");
	}
	return 0;
}