[Bronze V][JAVA]11050번:이항 계수1

11050번:이항 계수1 - 문제 풀러가기

이항계수

이항계수란 주어진 집합에서 원하는 개수만큼 순서없이 뽑는 조합의 개수를 의미한다. 여기서 이항 이란 한 개의 아이템에 대해서 뽑거나 뽑지않거나 두가지의 선택이 있기 때문에 붙은 단어이다. 이항계수의 정의는 다음과 같이 표현된다.

성질

파스칼의 삼각형
위의 ..3은 파스칼의 삼각형과 관련이 깊다.

• 각 행의 첫 번째와 마지막의 숫자는 1이다
• 파스칼의 삼각형 속의 숫자들은 바로 윗 줄에 인접하는 두 숫자의 합으로 정의된다.

구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main { //문제유형: 조합론 , 메모리 제한: 256MB, 시간 제한: 1초
    public static void main(String arg[]) 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 answer = fact(N) / (fact(N - K) * fact(K));
        System.out.println(answer);
    }

    public static int fact(int n) {
        if (n <= 1) {
            return 1;
        }
        return n * fact(n - 1);
    }
}