[11050] 이항 계수 1

자연수 (N)과 정수 (K)가 주어졌을 때 이항 계수를 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 (N)과 (K)가 주어진다. (1 ≤ (N) ≤10, 0 ≤ (K) ≤ (N))

출력

• 이항계수 출력

생각

참고
세 가지 방법이 있다고 한다.

1. 이항계수의 정의를 이용하여 팩토리얼 사용.

• 단점: 큰 시간복잡도

2. 동적 계획법 1: 이항계수의 성질 이용

• 전체 집합에서 아무것도 고르지 않는 방법은 1가지이고, 동시에 모두를 선택하는 것도 1가지 방법뿐이다. 그리고 3번 성질을 이용하면 이항계수를 그보다 작은 두 개의 부분식으로 쪼갤 수 있고 이 식들은 더 잘게 계속계속 쪼개질 수 있다. 쪼개지면서 n과 k가 점차 작아지는데 k가 0이 되는 순간과 n과 k가 같아지는 순간은 무조건 1이다. 성질에 의해 정의된 것이니까.
• 단점: 부분문제의 중복으로 함수의 성능이 좋지 않다.

3. 동적 계획법 2: 완전탐색

• n 에 대해 k 개의 아이템을 뽑는다…는 경우의 수는 조금만 달리 생각하면 아이템을 선택할 기회가 n 번 있을 때 결국 k 개를 뽑았을 경우의 수와 일치한다. 같은 말 아닌가 하고 말할 수 있지만 후자는 각 기회가 분리될 수 있다.
  주어진 기회는 n 번이며 각 기회에서 우리가 선택할 수 있는 전략은 1. 선택하거나, 2. 선택하지 않거나 이다.
  우리는 0번에서 시작해서 한 번씩 선택하며, 결국 n 번째까지 선택했을 때 k 개가 선택된 경우의 수를 알고 싶다.
  그렇다면, 0번째부터 시작해서 각 단계마다 하나를 선택하거나 선택하지 않는 방법을 모두 계산해서 최종적으로 k 개가 모인 경우만 세보자.

... 이라는데 결론은 각 케이스 별로 선택하냐 하지 않느냐가 합쳐진 경우의 수를 구하는 것이다.
DFS 알고리즘과 재귀 함수를 이용하면 될것이라고 생각한다.

처음 코드

namespace SongE
{
    public class Program
    {
        static int[,] dy;
        static int DFS(int n, int r)
        {
            if (dy[n, r] > 0) return dy[n, r];
            if (r == 0 || n == r) return 1;
            else return dy[n, r] = DFS(n - 1, r) + DFS(n - 1, r - 1);
        }
        static void Main(string[] args)
        {
            using var input = new System.IO.StreamReader(Console.OpenStandardInput());
            using var print = new System.IO.StreamWriter(Console.OpenStandardOutput());

            int[] n = Array.ConvertAll(input.ReadLine().Split(), s => int.Parse(s));

            dy = new int[n[0] + 1, n[1] + 1];

            print.Write(DFS(n[0], n[1]));  
        }
    }
}