[JAVA] 백준 11050번: 이항 계수 1

 

---

문제

• 자연수 N과 정수 K가 주어졌을 때 이항 계수를 구하는 문제.

 

아이디어

• 있는 그대로 구현한다.
• N! / K! * (N-K)! 이므로 분자의 N * N-1 * ... * N-K+1 만 따로 계산해놓는다.

 

풀이

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

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());

        int answer = 1;
        // N x (N-1) x ... x (N-K+1) 
        for(int i=K+1; i<N+1; i++) {
            answer *= i;
        }
        // 나머지 (N-K)!으로 나눔
        for(int i=1; i<N-K+1; i++) {
            answer /= i;
        }
        System.out.println(answer);
    }
}

 

 

채점 결과

11050번 채점 결과

기타

•   동적 계획법으로 구현할 수도 있다는데... 더 공부가 필요한 것 같다.

 

문제 링크

• 11050번: 이항 계수 1 (acmicpc.net)