[BaekJoon] 11050번 - 이항 계수 1 [Java]

문제 링크

---

문제 풀이

자연수 $N$ 과 정수 $K$ 가 주어졌을 때 이항 계수를 구하는 문제로 파스칼의 항등식을 활용한 재귀로 해결할 수 있다.

파스칼의 삼각형을 통해 알 수 있는 파스칼의 항등식은 아래와 같다.

\[\binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1}\]

종료 조건은 아래와 같이 설정해주면 된다.

\[\binom{n}{0} = \binom{n}{n} = 1 \qquad\text{and}\qquad \binom{n}{1} = n\]

---

코드

1. 풀이 [Java]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        System.out.println(nCr(N, K));
    }

    static int nCr(int n, int r) {
        if (r == 0 || n == r) return 1;
        if (r == 1) return n;

        return nCr(n - 1, r) + nCr(n - 1, r - 1);
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

int nCr(int n, int r) {
    if (r == 0 || n == r) return 1;
    if (r == 1) return n;

    return nCr(n - 1, r) + nCr(n - 1, r - 1);
}

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

    int n, k;
    cin >> n >> k;
    cout << nCr(n, k);
}

---