NYOJ176 정수 세그먼트(DP, DFS)

제목:

정수 구분 (2)

시간 제한:
1000ms | 메모리 제한:
65535 KB
난이도:
3
묘사
하나의 정수 m를 n개의 정수의 합으로 나누면 몇 가지 분법이 있습니까?
예: 5를 3개의 정수의 합으로 나누면 두 가지 분법이 있다.
1 1 3
1 2 2
입력
첫 번째 행은 총 T그룹 테스트 데이터를 나타내는 정수 T(T<=50)
각 그룹의 테스트 데이터는 두 개의 정수 m, n이다. 그 중에서 (1<=n<=m<=100)은 각각 분해할 정수와 분해할 정수의 개수를 나타낸다.
출력
분할 방법의 수를 출력합니다.
샘플 입력

2
5 2
5 3

샘플 출력

2
2

출처
[장운총] 오리지널
아이디어:
동적 계획:
먼저 DP의 사고방식을 고려하고 dp[m][n]를 정의하여 m개수에서 n개수를 구분하고 모두 방안수를 표시한다.
그러면 우리는 먼저 하나의 수가 1인 상황을 고려한다. dp[n-1][m-1]: 만약에 하나의 수가 1이 존재한다면 우리는 1을 이 m개의 수 맨 앞에 두면 m-1개의 수를 구분해야 한다. 이때 구분해야 할 값은 n-1이다. 왜냐하면 하나의 수가 확정되었기 때문에 얻을 수 있다.
만약 구분된 수에 1이 포함되지 않는다면, 우리는 먼저 이 구분된 수에 1을 빼면, 그들의 값이 2보다 크다는 것을 보장할 수 있다.그럼 dp[n-m][m]
그래서 상태 이동 방정식은 dp[i][j]=dp[i-1][j-1]+dp[i-j][j]
반복:
위의 게이지와 생각이 많이 다르지 않으니 코드를 보면 알 수 있다
코드 1(dp)
4

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define mod 10000007
#define debug() puts("what the fuck!!!")
#define ll long long
using namespace std;
int main()
{
	int i,j,t;
	int dp[105][105]= {1};
	for(i=1; i<=100; i++)
		for(j=1; j<=i; j++)
			dp[i][j]=dp[i-j][j]+dp[i-1][j-1];
	scanf("%d",&t);
	while(t--)
	{
		int n,k;
		scanf("%d%d",&n,&k);
		printf("%d
",dp[n][k]);
	}
}

코드2(재귀)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define mod 10000007
#define debug() puts("what the fuck!!!")
#define ll long long
using namespace std;
int f(int m,int n)
{
	if(m==n||n==1)  return 1;
	else if(mn)    return f(m-1,n-1)+f(m-n,n);
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int m,n;
		scanf("%d%d",&m,&n);
		printf("%d
",f(m,n));
	}
	return 0;
}