백준 11050 이항 계수1 [JAVA]

문제 해석

• 문제는 고등학교에서 배우는 조합론의 이항 계수를 구하는 문제이다.
• 이항계수(Binomial Coefficient)는 조합론에서 등장하는 개념으로 주어진 크기 집합에서 원하는 개수만큼 순서없이 뽑는 조합의 가짓수를 말하는데, 쉽게 말하면 전체 집합에서 원소의 개수 n에 대해 k개의 아이템을 뽑는 것을 의미한다.
  
• 이항계수를 구하는 위의 식은 다음과 같은 점화식(어떤 수열의 각각의 항들의 관계를 나타낸 식)이 성립한다.
  

만약 {1, 2, 3, 4, 5}가 주어질 때, 3개를 뽑는다고 가정하자.

원소 1를 기준으로 생각해봤을 때, 

원소 1를 선택 한 경우 : 나머지 4개 중에서 2개를 선택 ₄C₂

원소 1을 선택하지 않은 경우 : 나머지 4개 중에서 4개를 선택 ₄C₄
 
-> 각각의 경우의 수를 더한 결과가 ₅C₃의 모든 경우가 되므로 

₅C₃ = ₄C₂ + ₄C₄ 으로 표현할 수 있고 위의 점화식이 잘 성립함을 알 수 있다.
 

코드

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken()); //n
        int k = Integer.parseInt(st.nextToken()); //k

        br.close();

        //이항 계수 구하는 공식
        bw.write(factorial(n)/(factorial(k)*(factorial(n-k))) + "\n");

        bw.flush();
        bw.close();
    }

    //팩토리얼 구하는 공식
    static int factorial(int num)
    {
        int result = 1; //0과 1 팩토리얼은 1이기 때문에 1부터 시작

        for(int i = 2; i <= num; i++)
        {
            result = result * i;
        }
        return result;
    }
}

결과

느낀 점

• 이항 계수를 안본지 꽤 되어서 기억이 하나도 안나 어려움이 있었다.
• 진짜 수학공부를 다시해야하나... 심히 걱정이 된다.🥹