[백준] BOJ_11050, 11051 이항계수 JAVA

BOJ_11050 이항 계수 1
BOJ_11051 이항 계수 2

문제

(링크 참조)

---

입력

(링크 참조)

---

출력

(링크 참조)

---

예제 입&출력

(링크 참조)

---

소스코드

• 이항 계수 1

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int k = sc.nextInt();

        long start = System.currentTimeMillis();
        System.out.println(bc(n,k));
        long end = System.currentTimeMillis();
        System.out.println(end-start);
    }

    private static int bc(int n, int k) {
        return factorial(n) / (factorial(n - k) * factorial(k));
    }

    private static int factorial(int value) {
        int ans = 1;

        if (value == 0) return 1;

        for (int i = value; i >= 1; --i) {
            ans *= i;
        }

        return ans;
    }
}

• 이항 계수 2

import java.util.Scanner;

public class Main {

    private static int[][] memo;
    private static final int NUM = 10_007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int k = sc.nextInt();

        memo = new int[1001][1001];

        for (int i = 0; i <= n; i++) {
            //(2')
            memo[i][0] = 1;
            memo[i][i] = 1;
        }

        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= i; j++) {
                if (i == j || j == 0) {
                    //(2')
                    memo[i][j] = 1;
                } else {
                    // (3)
                    memo[i][j] = memo[i-1][j] + memo[i-1][j-1]; 
                }

                memo[i][j] %= NUM;
            }
        }

        System.out.println(memo[n][k]);
    }
}

---

Comment

• 문제 1과 문제 2의 차이는 입력 범위이다. 제한 시간 이내에 1번의 코드로 2번을 풀 수 없다.
• 문제 2는 Dynamic Programming(DP)를 사용했다.
• 💖이항계수의 몇 가지 성질에 대해 알아보자.
  • (1)
    
  • (2) & (2')
    
    
  • (3)
    
  • 위와 같은 성질들을 통해서 dp로 구현했다.

---