[BaekJoon 11050][🟤1] 이항 계수 1

❓ 문제

백준 11050 - “이항 계수 1”

🎯 난이도

Bronze 🟤1

🧠 풀이

1. 내 풀이 (이항 계수 - 팩토리얼)

- 알고리즘

• Combinatorics, Mathematics

- 설명

팩토리얼 수학 기법을 사용한 풀이이다.

이항 계수의 가장 기본적인 식을 사용했다. 그 식은 다음과 같다.

\[\binom{n}{r} = \frac{n!}{r! (n - r)!}\]

팩토리얼 구현은 재귀가 아닌 반복문으로 구현했고, 혹시 모를 오버플로우를 염두에 두어 long long 자료형을 사용했다.

팩토리얼 한번에 O(N)이므로 전체적인 시간 복잡도는 O(N)이다.

- 코드

내 풀이 코드

#include <iostream>


using namespace std;

typedef long long ll;

ll Facto(ll llStart);

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll llN{}, llK{};
    cin >> llN >> llK;

    cout << Facto(llN) / (Facto(llK) * Facto(llN - llK));

    return 0;
}

// 팩토리얼 구현 함수
ll Facto(ll llStart)
{
    ll llResult{ 1 };

    for(ll i = 2; i <= llStart; ++i)
    {
        llResult *= i;
    }

    return llResult;
}

---

2. 추가 풀이 1 (이항 계수 - 파스칼의 삼각형)

- 알고리즘

• Combinatorics, Mathematics, Dynamic Programming

- 설명

이항 계수의 파스칼의 삼각형 정리를 사용한 방식이다.

• 파스칼의 삼각형 정리는 다음과 같다.

\[C(n, k) = C(n - 1, k - 1) + C(n - 1, k)\]

• 또한 이항 계수의 기본적인 성질 중에 다음과 같은 것이 있다.

\[C(n, 0) = C(n, n) = 1\]

따라서 위의 두 식을 이용하면 'DP 식'을 세워 문제를 해결할 수 있다.

이렇게 하면 N이 커지는 경우의 오버플로우에 대해 걱정하지 않아도 되므로 사실상 가장 보편적이고 정석에 가까운 방법이다.

이중 반복문을 사용하므로 시간 복잡도는 O(N²)이지만 N이 작은 경우 O(N)과 크게 차이가 없다.

- 코드

내 풀이 코드

#include <iostream>


using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int iN{}, iK{};
    cin >> iN >> iK;

    int arrC[11][11]{};

    for(int i = 0; i <= iN; ++i)
    {
        arrC[i][0] = arrC[i][i] = 1;

        for(int j = 1; j < i; ++j)
        {
            arrC[i][j] = arrC[i - 1][j - 1] + arrC[i - 1][j];
        }
    }

    cout << arrC[iN][iK];

    return 0;
}

---

3. 추가 풀이 2 (이항 계수 - 팩토리얼 최적화)

- 알고리즘

• Combinatorics, Mathematics

- 설명

위의 내 풀이에서 팩토리얼 부분을 최적화한 방식이다.

• 이항 계수의 정리에서

\[\binom{n}{r} = \frac{n!}{r! (n - r)!}\]

• 부분을 다음과 같이 변환할 수 있다.

\[\binom{n}{r} = \frac{n \cdot (n + 1) \cdots (n - k + 1)}{k!}\]

• 그리고 이는 다시 다음과 같이 표현할 수 있다.

\[\binom{n}{r} = \varPi_{i = 1}^{k} \frac{n - k + i}{i}\]

이 방식으로 팩토리얼을 최적화해주면, 계산 중간에 오버플로우가 발생하는 것을 방지할 수 있으므로 더욱 범용적이고 안전한 방법이다.

팩토리얼의 계산 중간 오버플로우를 방지하는 최적화일 뿐이므로 시간 복잡도는 여전히 O(N)이다.

- 코드

내 풀이 코드

#include <iostream>


using namespace std;

typedef long long ll;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll llN{}, llK{};
    cin >> llN >> llK;

    // 더 작은 값 선택해서 반복문 최적화
    llK = llK > llN - llK ? llN - llK : llK;

    ll llResult{ 1 };

    for(ll i = 1; i <= llK; ++i)
    {
        // long long의 오버플로우 방지할 수 있다.
        llResult = llResult * (llN - llK + i) / i;
    }

    cout << llResult;

    return 0;
}

---

💭 후기

사실 조합론에 대해서는 잘 알지 못했고, 이런 문제는 아예 이 알고리즘에 대해 알지 못하면 풀지 못하는 문제이다.

또한 조합론엔 여러 정리와 성질, 변형이 있으므로 잘 숙지해두는 것이 좋을 듯하다.

🔗 참고자료

• 이항 계수