✅백준 11050번: 이항 계수 1 (C#)

오늘은 백준 11050번 문제를 풀면서 이항 계수(binomial coefficient) 개념을 처음으로 제대로 알게 됐다.

https://www.acmicpc.net/problem/11050

📌 이항 계수란?

이항 계수는 n개 중에서 k개를 뽑는 경우의 수를 의미한다. 수학적으로는 아래의 공식으로 계산된다.

여기서 !는 팩토리얼(factorial)을 의미한다. 예를 들어 5! = 5 × 4 × 3 × 2 × 1 = 120 이다.
또한 0!은 정의상 1로 약속되어 있다.

📌 주의할 점

처음에 헷갈렸던 부분이 (n - k)! 부분이었다.
나는 단순히 n! / k! * (n - k)라고 오해했는데, (n - k)!는 n - k를 계산한 다음 팩토리얼을 취하는 것이라는 걸 알게 됐다.
즉, n = 5, k = 2이면:

그리고 중요한 점은, n이 k보다 작을 수 없다는 것이다.
예를 들어 n = 2, k = 5이면 (2 - 5)! = (-3)!가 되는데,
음수의 팩토리얼은 수학적으로 정의되지 않기 때문에 이항 계수도 계산할 수 없다.

실제로 프로그래밍에서는 이런 경우 0으로 처리하는 것이 일반적이다.

using System;

class Program
{
    static void Main()
    {
        string[] input = Console.ReadLine().Split();
        int n = int.Parse(input[0]);
        int k = int.Parse(input[1]);

        Console.WriteLine(BinomialCoefficient(n, k));
    }

    static int Factorial(int num)
    {
        int result = 1;
        for (int i = 2; i <= num; i++)
        {
            result *= i;
        }
        return result;
    }

    static int BinomialCoefficient(int n, int k)
    {
        if (k > n) return 0; // 잘못된 입력 처리
        return Factorial(n) / (Factorial(k) * Factorial(n - k));
    }
}

💡 배운 점

이항 계수의 수학적 의미와 공식을 처음으로 제대로 이해했다.

팩토리얼 개념이 중요하고, (n - k)!는 n - k를 먼저 계산한 뒤에 팩토리얼을 취해야 한다.

n < k인 경우는 조합이 불가능하므로 반드시 체크해야 한다.