[BaekJoon] 11050 이항 계수 1 JAVA

🔗 백준 11050 문제 https://www.acmicpc.net/problem/11050

문제

자연수 $N$과 정수 $K$가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\))

---

출력

\(\binom{N}{K}\)를 출력한다.

---

풀이

이항계수

• 두개의 항을 전개하여 계수로 나타낸 것
• 즉, (a + b)ⁿ 을 전개하였을 때 계수를 의미

예를 들어  (a + b)² = a² + 2ab + b² 이고 계수는 1, 2, 1 이다.

 

파스칼 삼각형

사실.. 수포자라 이항계수 이해가 잘 가지 않았다.

 

결국엔 nCr이기때문에 factorial을 사용하거나 동적계획법을 사용해야한다는거 같은데..

헷갈리는 나머지 factorial 기본 알고리즘부터 DP, 그리고 Bottom-Up까지 코드를 구현해봤다.

 

내가 푼 코드

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

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(factorial1(n) / (factorial1(n - k) * factorial1(k)));
        System.out.println(factorial2(n, k));
        System.out.println(DP(n, k));
        System.out.println(BU(n, k));
    }
    
    // 알고리즘 1
    private static int factorial1(int n) {
        if (n <= 1) return 1;
        return n * factorial1(n - 1);
    }

    // 알고리즘 2
    private static int factorial2(int n, int k) {
        if (n == k || k == 0) return 1;
        return factorial2(n - 1, k - 1) + factorial2(n - 1, k);
    }

    // 알고리즘 2를 활용한 DP
    private static int DP(int n, int k) {
        int[][] dp = new int[n + 1][k + 1];

        // 이미 풀었던 문제일 경우 저장해둔 값 재활용 : 메모이제이션
        if (dp[n][k] > 0) return dp[n][k];

        // 2번 성질
        if (n == k || k == 0) return dp[n][k] = 1;

        // 1번 성질
        return dp[n][k] = DP(n - 1, k - 1) + DP(n - 1, k);
    }

    // Bottom-Up
    private static int BU(int n, int k) {
        int[][] dp = new int[n + 1][k + 1];

        // 2번 성질1 (n == k)
        for (int i = 0; i <= k; i++) dp[i][i] = 1;

        // 2번 성질2 (k == 0)
        for (int i = 0; i <= n; i++) dp[i][0] = 1;

        // 1번 성질
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= k; j++) dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
        }

        return dp[n][k];
    }
}