수 분할 [C 언어]

#include 
// 수분할

// partition(0, m) =1 
// partition(n,m) = i~m partition(n-i,i)
int partition(int n, int m)
{
  int count = 0, i;
  
  // n/m 수분할은 n/n 수문할과 같으므로 m에 n을 대입한다.
  // 5를 6까지 이용해서 분할할 수는 없으니까
  if (n < m) {
    // printf("n=%d, m=%d\n", n, m);
    m = n;
  }
  if (n == 0) // Base Case 0
    return 1;

  for (i = 1; i <= m; i++) {
    // printf("call partition(%d, %d);\n", n-i, i);
    count += partition(n - i, i);
  }
  return count;
}

#define MAX 1000
int partition_cache(int n, int m)
{
  static int cache[MAX][MAX];
  int count = 0, i;
  
  if (n < m) {
    m = n;
  }
  if (cache[n][m]) {
    return cache[n][m];
  }
  if (n == 0) {
    return cache[n][m] = 1;
  }
  
  for (i = 1; i <= m; i++) {
    count += partition_cache(n - i, i);
  }
  
  return cache[n][m] = count;
}

int main(void) {
  // printf("first %d\n", partition(1000,4));
  printf("second %d\n",  partition_cache(1000, 4));
  return 0;
}