제 38, 다항식의 계수, Polynomial Coefficients, PC/UVa ID : 110506/10105, 인기도 : B, 성공률 : 높음, 레벨 : 1

이 포스트를 만든 목적

  • 생각 절차, 푼 방법, 고민거리 등을 기록하기 위해서 만들었다.

이 포스트의 준비물

  • Mozila Firefox 5.0 beta
  • eclipse 3.6.1 + vrapper
  • java

참조 문헌

  • 스티븐 스키에나, 미구엘 레비야 저. Programming Challenges: 알고리즘 트레이닝 북. 서환수 역.
    Springer. 한빛미디어 초판 2쇄 2004.12.05. (문제 38, 다항식의 계수, Polynomial Coefficients, p.158)

참조 링크

간략한 이야기/프로그램의 입출력

이 문제는 다항식 (x1+x2+...+xk)n을 전개했을 때 계수를 구하는 것이다.

입력

  • 여러 쌍의 줄이 입력된다.
  • 각 쌍의 첫번째 줄에는 두 개의 정수 n과 k가 있으며, 그 두 정수는 스페이스로 구분된다. (0<k, n<13)
  • n은 다항식의 제곱이고, k는 단항식의 갯수이다.
  • 각 쌍의 두번째 줄에는 k개의 음이 아닌 정수 n1, ..., n수가 입력되며, 이때 n1+...+nk=n 이다.
    이때 n1, ..., n 는 단항식의 각 문자의 지수를 뜻한다.

출력

  • 입력된 각 줄의 쌍에 대해 하나의 정수를 출력한다.
  • 출력된 이 정수는 (x1+x2+...+xk)n 를 풀었을 때 나오는 x1n1x2n2...xknk의 계수이다.
맛보기 코드


맛보기 사진


여담

  • 수학1 에서 이항 정리에 대한 설명이 있다.
  • 이 문제를 풀려면 "다항 정리"를 해야만 한다. (수학1에 간단하게 공식만 있다.)
  • 문제 이해하는데 많은 시간이 걸렸고, 이해 후 풀려는데 다항정리가 필요하다는 것에 시간이 걸렸다.
  • 다른 사람이 푼것들, 답지를 보고 배울점은 팩토리얼의 최대치까지 미리 구해놓고 쓴다는 부분이다.

:wq!

  • 네이버 블러그 공유하기
  • 네이버 밴드에 공유하기
  • 페이스북 공유하기
  • 라이프코리아트위터 공유하기
  • shared
  • 카카오스토리 공유하기