[11050] 이항 계수 1

✔ 이항 계수 1

[백준 11050]

문제 분석하기

조합에서 가장 기본이되는 문제이므로 일반 점화식을 이용하여 문제를 해결

손으로 풀어보기

1. N과 K의 값을 입력받고 DP 배열을 선언
   • D[N + 1][N + 1]
2. DP 배열의 값을 초기화
   • i개 중 1개를 뽑는 경우의 수인 D[i][1] = i
   • i개 중 0개를 뽑는 경우의 수인 D[i][0] = 1
   • i개 중 i개를 뽑는 경우의 수인 D[i][i] = 1
3.  점화식으로 DP 배열의 값을 채움
   • D[i][j] = D[i - 1][j] + D[i - 1][j - 1]
4. D[N][K]의 값을 출력함

슈도코드 작성하기

N(총 개수), K(선택 수)
D(DP 배열)
for(i -> N만큼 반복하기) {
    D 배열 초기화하기
    D[i][1] = i
    D[i][0] = 1
    D[i][i] = 1
}
for(i -> N만큼 반복하기) {
    for(j -> i만큼 반복하기) {
        D[i][j] = D[i - 1][j] + D[i - 1][j - 1]
    }
}
D[N][K]

코드 구현하기

/**
 * 11050) 이항_계수_1
 */
public class D076_11050 {
    static int N, K;
    static int[][] D;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // N(총 개수)
        N = sc.nextInt();
        // K(선택 수)
        K = sc.nextInt();
        // D(DP 배열)
        D = new int[N + 1][N + 1];
        // D 배열 초기화하기
        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]);
    }
}