[백준] 11050번 - 이항 계수 1 [Java]

문제 링크

---

문제 풀이

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

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

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

1. 재귀

nCr의 값을 리턴하는 메서드를 작성하고 반환값에 해당 항등식을 적용하면 된다. 종료 조건은 아래 식을 통해 설정하면 된다.

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

메모이제이션을 활용한 Top-Down dp로 해결해도 된다.

2. Bottom-Up dp

파스칼의 삼각형을 2차원 dp 배열로 구현하면 되며 행을 $N$, 열을 $K$ 라 했을 때, 아래 점화식으로 이항 계수를 구할 수 있다.

\[dp[n][r] = dp[n-1][r] + dp[n-1][r-1]\]

---

코드

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));
    }

    private 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. Bottom-Up dp [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());

        int[][] dp = new int[1 + N][1 + K];
        for (int n = 0; n <= N; n++) {
            dp[n][0] = 1;

            for (int r = 1; r <= Math.min(n, K); r++) {
                dp[n][r] = dp[n - 1][r] + dp[n - 1][r - 1];
            }
        }

        System.out.println(dp[N][K]);
    }
}

---

풀이 정보

1. 재귀 [Java]

• 4 min

2. Bottom-Up dp [Java]

• 6 min

---