이항 계수 1 (백준 11050)

1초

256 MB

문제

자연수 N과 정수 K가 주어졌을 때 이항 계수 nCk를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 정수 K가 주어진다. ( 1 ≤ N ≤ 10, 0 ≤ K ≤ N )

출력

nCk를 출력한다.

---

<생각의 흐름>

조합에서 가장 기본이 되는 문제로 일반 점화식을 이용하면 이 문제를 해결할 수 있음

DP배열에는 항상 의미가 있어야하고 이해해야한다
이 문제에서는 D[i][j]에서 i는 총숫자 갯수, j는 선택수 갯수
즉 i개중 j개를 뽑았을 때 조합 경우의 수를 표현하는 것임

점화식 필요없이 기본적으로 알수있는 것들은 초기화를 함
D[i][1] = i , D[i][0] = 1 , D[i][i] = 1 , 총갯수보다 선택수가 큰 경우는 0으로 setting

조합 점화식 D[i][j] = D[i-1][j]+D[i-1][j-1]  

 

<코드>

import java.io.IOException;
import java.util.Scanner;

public class Main {
    static int N,K;
    static int D[][];
    public static void main(String[] args) throws IOException {

        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        K = sc.nextInt();
        D = new int[N+1][N+1];

        //초기화
        for(int i =0; i<=N ; i++){
            D[i][1] = i;
            D[i][0] = 1;
            D[i][i] = 1;
        }

        // 점화식으로 배열 완성하기
        for(int i=2; i<=N ; i++){
            for(int j = 1; j < i; j++){
                D[i][j] = D[i-1][j]+D[i-1][j-1];
            }
        }
        System.out.println(D[N][K]);
    }
}

---

<피드백>

...