사과 넣기

마늘은 같은 사과 M개를 N개의 같은 접시에 넣고 어떤 접시를 비우고 놓지 않는 것을 허락하는데 모두 몇 가지 다른 분법이 있는지 알고 싶다.(K로 표시) 5, 1, 1과 1, 5, 1은 같은 분법이다.
입력 형식의 첫 번째 줄은 테스트 데이터의 수 t(0≤t≤20)입니다.
다음 행에는 공백으로 구분되는 두 개의 정수 M과 N이 있습니다.1 ≤ M,N ≤ 10.
출력 형식은 입력한 각 데이터 M과 N에 대해 한 줄로 해당하는 K를 출력합니다.출력 시 각 줄 끝에 있는 빈 칸은 정답에 영향을 주지 않습니다. 샘플 입력 173 샘플 출력 8 문제 분석:
이 문제의 관건은 점차적인 함수다.
m개의 사과를 n개의 접시에 놓으면 함수를 apple(m, n)으로 정의합니다.
1.m=0, 사과가 없으면 한 가지 넣는 방법, 즉 apple(0,n)=1
2.n=1, 접시가 하나밖에 없어요. 사과가 있든 없든 간에 넣는 방법은 하나예요. apple(m,1)=1
3.n>m, m개의 사과를 m개의 접시에 놓는 것과 같다. 즉, apple(m, n)=apple(m, m)
4.m>=n, 이때 두 가지 상황으로 나뉜다. 하나는 모든 접시에 사과가 있고, 다른 하나는 모든 접시에 사과가 있는 것이다.모든 접시에 사과가 있는 것이 아니라 적어도 한 접시가 비어 있는 것과 같다. 즉, =apple(m, n-1)이다.모든 접시에 사과가 있다. 즉, 적어도 모든 접시에 사과가 하나 있다. m개의 사과 중 n개는 n개의 접시에 넣고 나머지 m-n개의 사과는 m-n개의 사과를 n개의 접시에 넣는 것과 같다. 즉, =apple(m-n, n)이다.이때 apple(m, n)=apple(m-n, n)+apple(m, n-1).
기억화 귀속의 해법을 추가하다.이 문제도 모함수로 풀 수 있는데, 모함수의 나체문제이다.
문제 풀이 사고방식1:

#include 
#include 
#include 
#include 
#include 
using namespace std;
int f(int m, int n){
    if (m == 0)return 1;
    if (n == 1)return 1;
    if (n > m){
    	return f(m, m);	
    }else{
        return f(m, n - 1) + f(m - n, n);
    }
}
int main(){
    int m,n;
    //while(scanf("%d%d",&m,&n) != EOF){
    while(~scanf("%d%d",&m,&n)){
        int ans = f(m, n);
        printf("%d
", ans);
    }
    return 0;
}

문제 풀이 사고방식2:

/* POJ1664   */
 
#include 
#include 
#define N 10
int a[N + 1][N + 1];
 
int apple(int m, int n)
{
    if(a[m][n])
        return a[m][n];
    else {
        if(m == 0 || n == 1)
            return a[m][n] = 1;
        else if(n > m)
            return a[m][n] = apple(m, m);
        else
            return a[m][n] = apple(m - n, n) + apple(m, n - 1);
    }
}
 
int main(void)
{
    memset(a, 0, sizeof(a));
 
    int t, m, n;
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &m, &n);
 
        printf("%d
", apple(m, n));
    }
 
    return 0;
}