Binomial Coefficient (iterative)

1. Problem

- nCk를 계산해보자.

 

2. Input

1) 음이 아닌 정수 n

2) 음이 아닌 정수 k

- 이때 k <= n

 

3. Output

1) nCk의 값

- C는 수학에서 조합을 나타내는 기호로, nCk는 n!/(k!(n-k)!)으로 계산된다.

 

4. PseudoCode

int bin2(int n, int k){
    index i, j;
    int B[0..n][0..k]
    for(i=0 ; i<=n ; i++){
        for(j=0 ; j<=minimum(i,k) ; j++){
            if(j==0 || j==i)
                B[i][j] = 1;
            else
                B[i][j] = B[i-1][j-1] + B[i-1][j];
        }
    }
    return B[n][k];
}

 

5. Example

class AlgoTest {
    public static void main(String[] args){
        System.out.println(bin2(5,3)); // 10
    }
    
    static long bin2(int n, int k) {
        int[][] B = new int[n+1][k+1];
        for(int i=0 ; i<=n ; i++) {
            for(int j=0 ; j<=Math.min(i, k) ; j++) {
                if(j==0 || j==i)
                    B[i][j] = 1;
                else
                    B[i][j] = B[i-1][j-1] + B[i-1][j];
            }
        }
        return B[n][k];
    }
}