정수 구분 문제 (귀속 법)

정수 구분 문 제 는 알고리즘 중의 전형 적 인 명제 중 하나 로 이 문제 에 대한 설명 은 재 귀 할 때 대체적으로 관련 될 것 이다.정수 구분 이란 하나의 정수 n 을 다음 과 같은 형식 으로 쓰 는 것 을 말한다.
    n=m1+m2+...+mi; (그 중에서 미 는 정수 이 고 1 < = 미 < = n) 는 {m1, m2,..., 미} 은 n 의 구분 이다.
{m1, m2,..., mi} 의 최대 값 이 m, 즉 max (m1, m2,..., mi) < = m 를 초과 하지 않 으 면 n 의 m 구분 이 라 고 합 니 다.여기 서 우리 가 n 의 m 로 나 눈 개 수 는 f (n, m) 이다.
예 를 들 어 n = 4 시 에 그 는 5 개의 구분 이 있 는데 {4}, {3, 1}, {2, 2}, {2, 1, 1}, {1, 1, 1, 1};
주의 4 = 1 + 3 과 4 = 3 + 1 은 같은 구분 으로 여 겨 진다.
이 문 제 는 n 의 모든 구분 개수, 즉 f (n, n) 를 구 하 는 것 이다.다음은 f (n, m) 를 구 하 는 방법 을 고려 합 니 다.
1. 귀속 법:
   n 과 m 의 관계 에 따라 다음 과 같은 몇 가지 상황 을 고려한다.
   (1) n = 1 일 때 m 의 값 이 얼마 든 (m > 0) 한 가지 구분 만 {1};
   (2) m = 1 일 때 n 의 값 이 얼마 든 n 개 1, {1, 1, 1, 1..., 1} 만 나 눌 수 있 습 니 다.
   (3) n = m 일 때 구분 에 n 이 포함 되 어 있 는 지 여부 에 따라 두 가지 상황 으로 나 눌 수 있다.
      (a) 구분 에 n 이 포 함 된 경우 {n} 만 있 습 니 다.
      (b) 구분 에 n 이 포함 되 지 않 은 경우, 이때 구분 에서 가장 큰 숫자 도 n 보다 작 을 것 이다. 즉, n 의 모든 (n - 1) 구분 이다.
      따라서 f (n, n) = 1 + f (n, n - 1);
   (4) n < m 일 때 구분 에서 마이너스 가 나타 날 수 없 기 때문에 f (n, n) 에 해당 합 니 다.
   (5) 단 n > m 시 구분 에 최대 치 m 가 포함 되 어 있 는 지 여부 에 따라 두 가지 상황 으로 나 눌 수 있 습 니 다.
       (a) 구분 에 m 를 포함 하 는 경우, 즉 {m, {x1, x2,... xi}, 그 중 {x1, x2,... xi} 의 합 은 n - m 이기 때문에 이 경우
          f (n - m, m)
       (b) 구분 에 m 가 포함 되 지 않 은 경우 구분 에 있 는 모든 값 이 m 보다 작 습 니 다. 즉, n 의 (m - 1) 구분, 개 수 는 f (n, m - 1) 입 니 다.
      따라서 f (n, m) = f (n - m, m) + f (n, m - 1);
      위 에서 말 한 바 와 같이:
                             f(n, m)=   1;              (n=1 or m=1)
               f(n,m)   =    f(n, n);                   (n                             1+ f(n, m-1);              (n=m)
                             f(n-m,m)+f(n,m-1);         (n>m)

#include<iostream>
using namespace std;

int equationCount(int n,int m)
{
    if(n==1||m==1)
        return 1;
    else if(n<m)
        return equationCount(n,n);
    else if(n==m)
        return 1+equationCount(n,n-1);
    else
        return equationCount(n,m-1)+equationCount(n-m,m);
}

int main(void)
{
    int n;
    while(scanf("%d",&n)!=EOF&&(n>=1&&n<=120))
    {
        printf("%d
",equationCount(n,n));
    }
    return 0;
}