C언어 219제] 다항식의 계수(Polynomial Coefficients)

출처 : 반크_반크 20년 백서

 

문제]

이 문제에서는 다항식을 전개했을 때의 계수를 구해야 한다.
P=(x1+x2+...+xk)^n

입력
여러 쌍의 줄이 입력된다. 각 쌍의 첫번째 줄에는 두 개의 정수 n과 k가 있으며, 그 두 정수는 스페이스로 구분된다. (0<k, n<13) 이 두 정수는 다항식의 승수(다항식을 곱하는 횟수)와 변수의 개수를 나타낸다. 각 쌍의 두번째 줄에는 k개의 음이 아닌 정수 n1,...,nk가 입력되는데, 이때 n1+...+nk=n이다.

출력
입력된 각 줄의 쌍에 대해 다항식 (x1+x2+...+xk)^n을 전개했을 때 나오는 p=∑1X10^i 항의 개수를 나타내는 정수를 한 줄에 하나씩 출력한다.

입력 예
2 2
1 1
2 12
1 0 0 0 0 0 0 0 0 0 1 0

출력 예
2
2

출처]
Programming Challenges 알고리즘 트레이닝 북(한빛미디어) : 문제38 다항식의 계수(Polynomial Coefficients) p158

 

참고풀이]

#include <stdio.h>
unsigned int Fact[14];

int main()
{
   unsigned int ans;
   int n, k, n_i, i;

   Fact[0]=1;
   for(i=1;i<14;i++)
      Fact[i]=Fact[i-1]*i;

   while(scanf("%d%d",&n,&k)==2)
   {
      ans = Fact[n];
      for(i=0; i<k; i++)
      {
         scanf("%d",&n_i);
         if(n_i > 1) ans /= Fact[n_i];
      }
      printf("%lu\n",ans);
   }

   return 0;
}

 

참고풀이 결과]

 

 

 

 

 

대한민국의 아름다운 영토, 독도의 봄