문제 출처

단계별로 풀어보기 > 조합론 > 이항 계수 1
https://www.acmicpc.net/problem/11050

문제 설명

자연수 N, 정수 K가 주어졌을 때, 두 수의 이항 계수를 구하여라

접근 방법

팩토리얼 메서드를 생성하여 결과로 N!/((N-K)! x k!)의 결과를 return 한다.

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

public class 이항_계수_1 {
    public static int fact(int k){
        int result = 1;
        for(int i = 1; i<=k; i++){
            result*=i;
        }
        return result;
    }

    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());
        int K = Integer.parseInt(st.nextToken());

        int result = fact(N)/(fact(N-K)*fact(K));

        bw.write(String.valueOf(result));
        bw.flush();
        bw.close();
        br.close();
    }
}

Review

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

public class 이항_계수_1_review {

    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 dp[][] = new int[10][10];

        for(int i = 0; i<10; i++){
            dp[i][0] = 1;
            dp[i][i] = 1;
        }

        for(int j = 2; j<10; j++){
            for(int k = 1; k<10; k++){
                dp[j][k] = dp[j-1][k-1] + dp[j-1][k];
            }
        }
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        bw.write(String.valueOf(dp[N][K]));
        bw.flush();
        bw.close();
        br.close();
    }
}

알게된 점

조합론을 풀 때는 동적 계획법을 이용하여 풀이한다.

문제푼 흔적

Review