백준 11050번 [이항 계수 1](C++)-yes6686- 티스토리

백준 문제 풀이: 11050 [이항 계수 1]

---

문제 링크: https://www.acmicpc.net/problem/11050

문제 설명:

자연수 n과 정수 k가 주어질 때, 이항 계수 C(n, k)를 계산하는 문제입니다. 이항 계수는 조합의 개수를 의미하며, 아래의 식으로 정의됩니다:

C(n, k) = n! / (k!(n-k)!)

이 문제에서는 재귀적으로 이항 계수를 구하는 방법을 사용합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

// 재귀적으로 이항 계수 계산
int combination(int n, int k) {
    if (n == k || k == 0) return 1; // 기저 조건
    else {
        return combination(n - 1, k) + combination(n - 1, k - 1); // 재귀 관계
    }
}

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

    int n, k;
    cin >> n >> k;

    // 결과 출력
    cout << combination(n, k);
    return 0;
}

---

코드 설명

• 핵심 알고리즘: 재귀를 이용하여 이항 계수를 계산합니다.
• 구현 세부사항:
  • 기저 조건:
    • n == k인 경우: C(n, k) = 1
    • k == 0인 경우: C(n, k) = 1
  • 재귀 조건:
    • C(n, k) = C(n-1, k) + C(n-1, k-1)
• 시간 복잡도: O(2^n)
  • 재귀적으로 모든 경우를 계산하기 때문에 비효율적입니다. 큰 n에서는 동적 계획법을 사용하는 것이 효율적입니다.

---

결과

주어진 n과 k에 대해 이항 계수를 계산하고 출력합니다. 재귀를 통해 간단히 구현할 수 있지만, 시간 복잡도가 높아 입력 크기가 커질 경우 비효율적일 수 있습니다. 동적 계획법을 이용해 최적화할 수 있습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!