[ 조합 ] 조합(백준 11050)

 조합

조합은 _nC_r로 표현되고, n개의 숫자 중 r개를 뽑는 경우의 수를 뜻한다.

순열은 _nP_r로 표현되고, n개의 숫자 중 r개를 뽑아 순서를 고려해 나열할 경우의 수를 말한다.

 

💡 순열과 조합의 핵심 이론

🔍  순열

예를 들어, 5개중 순열을 이용해 3개를 뽑으면 (5*4*3*2*1)/(2*1)의 결과값이 나온다.

순열의 수학적 공식

 

 

🔍  조합

예를 들어, 5개중 조합을 이용해 3개를 뽑으면 (5*4*3*2*1)/(2*1)/(3*2*1)의 결과값이 나온다.

(2*1) -> 순서가 다른 경우의 수를 제거하는 역할

조합의 수학적 공식

 

 

☝🏻  조합 점화식 세우기

1️⃣ 특정 문제를 가정하기

5개의 데이터에서 3개를 선택하는 조합의 경우의 수 구하기

 

2️⃣ 모든 부분 문제가 해결된 상황이라고 가정하고 지금 문제 생각하기

먼저 5개의 데이터 중 4개는 이미 선택이 완료된 데이터일 때, 마지막 데이터의 선택 여부에 따른 경우의 수를 계산한다.

마지막 데이터를 선택 O -> 4개의 데이터 중 2개의 데이터 뽑기

마지막 데이터를 선택 X -> 4개의 데이터 중 3개의 데이터 뽑기 

 

5개 중 3개를 선택하는 경우의 수 점화식
₅C₃ = ₄C₂ + ₄C₃
D[5][3] = D[4][2] + D[4][3]

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

 

 

 11050 : 이항 계수 1

문제

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

 

입력

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

 

출력

이항계수를 출력한다.

입력	출력
5 2	10

 

문제 풀이

• 이항계수 : _NC_K를 구하는 문제이다
• DP[3][2] 부터 채운다 -> 기본 초기화에서 [n][0]과 [n][1]과 [n][n]이 모두 채워져있기 때문에

 

실행 코드

import java.util.Scanner;

public class P11050 {
    public static void main(String[] args) {
        //조합 점화식 : A[i][j] = A[i-1][j] + A[i-1][j-1]
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int[][] DP = new int[N+1][N+1];

        //기본 초기화
        for (int i = 0; i <= N; i++) {
            DP[i][1] = i;
            DP[i][0] = 1;
            DP[i][i] = 1;
        }
        for(int i=3;i<=N;i++){
            for(int j=2;j<=i;j++){
                DP[i][j] = DP[i-1][j-1] + DP[i-1][j];
            }
        }
        System.out.println(DP[N][K]);
    }
}