[Java] BOJ 이항 계수 1

문제 

문제 링크 https://www.acmicpc.net/problem/11050

• 자연수 N과 정수 K가 주어졌을 때 이항 계수 (N K)를 구하는 프로그램을 작성하시오.
• 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 0 ≤ K ≤ N)
• (N K)를 출력한다.

아이디어

• 조합 구하는 것이므로 구하는 식은 N! / (K! * (N - K)!) 이다. 따라서 팩토리얼을 다 계산해서 나눌 수도 있지만 K와 (N - K) 중에 더 큰 값을 구해서 그 값의 팩토리얼 값만큼은 안곱하고 그 뒤에 수부터 N까지 구한 뒤, 나머지 분모의 팩토리얼 값을 구해서 나누면 더 빠를 것이라고 생각했다. 
• 예를 들어 (5 3)이면 식이 (5! / (3! * 2!)일 것인데 3이 더크므로 5!을 계산할 때, 3!만큼 안 곱해주고 분모에 있는 3!을 없애주면 된다. (1*2*3*4*5 / (1*2*3 * 2!)이므로 공통된 1*2*3을 없애주는 것이다.) 그리고 남은 4*5 / 2!만 계산해주면 된다. 

겪은 시행착오

• X (처음에 부등호 실수를 해서 한번 틀렸지만 그래도 나름 쉽게 풀었다 ㅎㅎ)

ㅎㅎ

코드

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

public class BOJ11050 {
    public static void main(String[] args) throws Exception{
        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());

        // 조합을 구할때 N! / (K! * (N-K)!)이므로
        int K2 = N - K;
        // 결과값 저장할 변수
        int result = 1;
        // 팩토리얼 곱한 값 구할 변수
        int mul = 1;

        // 조합을 구할때 나누는 것이 K!과 (N-K)!이므로 더 큰쪽을 기준으로
        if(K >= K2){
            // 팩토리얼이 1부터 해당 수까지 모두 곱하는 것이기 때문에
            // 어차피 나눠야 될 수라면 처음부터 안곱하도록
            // 더 큰수보다 큰수부터 N까지 곱해서 저장
            for(int i = (K + 1); i <= N; i++){
                result = result * i;
            }

            // 나머지 작은 값을 팩토리얼 계산해줌
            for(int i = 1; i <= K2; i++){
                mul = mul * i;
            }

            // 위에 곱한수를 작은 값을 팩토리얼 계산한 값으로 나눠줌
            result = result / mul;
        }

        // 위와 같은 방식
        if(K2 > K){
            for(int i = (K2 + 1); i <= N; i++){
                result = result * i;
            }

            for(int i = 1; i <= K; i++){
                mul = mul * i;
            }

            result = result / mul;
        }

        System.out.println(result);
    }
}