NYOJ 279 팀 꽃의 고민 2와 NYOJ 176 정수 구분(二)[dp문제 또는 귀속]

원제 링크: 클릭.279를 클릭합니다.    176     
이 두 문제의 뜻은 기본적으로 같다. 바로 테스트 데이터의 범위가 다르다는 것이다.176 데이터는 비교적 물적이어서 일반적으로 시간을 초과하지 않지만, 279를 사용하면 시간을 초과할 수 있다.간단하게 dp로 문제를 푸는 사고방식을 말해 봅시다.
먼저 f(i, j)를 정수 i로 정의하여 j개의 정수로 나누는 상황...
분석을 통해 얻을 수 있는 f(i, j)는 두 부분으로 바뀔 수 있다.
1: 분할된 j개의 정수에 1이 포함되지 않는다고 가정합니다.그러면 이때 f(i-j, j)가 바로 이 부분의 전체 상황입니다.알겠어요?좀 더 똑똑히 말해봐.기왕 그가 1을 포함하지 못하게 하려면 먼저 j개의 정수를 모두 1로 나눈다. 이때 i는 i-j로 변한 다음에 i를 j개의 정수로 나눈다. 이 j개의 정수에 원래 나눴던 1을 더하면 틀림없이 다시는 1이 나타나지 않을 것이다.오케이 했지?
2: 가설적으로 나누어진 j개의 정수는 적어도 1개의 1이 있다.그러면 이때 f(i-1, j-1)가 바로 이 부분의 전체 상황입니다.그건 알겠지?글쎄요. 직접 분석해보세요.
결론: f(i, j) = f(i-j, j)＋f(i-1, j-1).동적 이동 방정식이 생겼으니 실현하기가 어렵지 않겠지...참, 초기화에는 아직 약간의 기교가 있다.스스로 궁리하다.그리고 문제의 데이터 범위가 그리 넓지 않기 때문에 폭력적인 해답이 빠를 것이다...
279 코드:

 
#include<stdio.h>
int main()
{
	int a,b,n,m,k;
	int ok[505][7]={0};
	ok[1][1]=1;
	for(a=2;a<=500;a++)
	{
		for(b=1;b<=a&&b<=6;b++)
			ok[a][b]=ok[a-b][b]+ok[a-1][b-1];
	}
	while(~scanf("%d%d",&n,&m))
	{	
		printf("%d
",ok[n][m]);
	}
}        

176 코드:

 
#include<stdio.h>
int main()
{
	int a,b,n,m,k;
	int ok[105][105]={0};
	ok[1][1]=1;
	for(a=2;a<=100;a++)
	{
		for(b=1;b<=a;b++)
			ok[a][b]=ok[a-b][b]+ok[a-1][b-1];
	}
	scanf("%d",&k);
	while(k--)
	{
		scanf("%d%d",&n,&m);
		printf("%d
",ok[n][m]);
	}
}