이항계수 구하기

N개의 수 중 K개를 선택하는 경우의 수를 구하는 방법은 점화식을 구하는 것에서 부터 시작합니다.

 

5개중 3개를 선택하는 경우의 수 점화식의 경우

D[5][3] = D[4][2] + D[4][3]

5개중 3개를 선택하는 경우의 수는

[4개의 수 중 2개를 선택한 경우의 수 + 4개의 수 중 3개를 선택한 경우의 수] 입니다. = 10

---

4개의 수 중 2개를 선택하는 경우의 수는

[3개의 수 중 1개를 선택한 경우의 수 + 3개의 수 중 2개를 선택한 경우의 수] = 6

 

4개의 수 중 3개를 선택하는 경우의 수는

[3개의 수 중 2개를 선택한 경우의 수 + 3개의 수 중 3개를 선택한 경우의 수] = 4

---

3개의 수 중 3개를 선택하는 경우의 수는

[2개의 수 중 2개를 선택한 경우의 수 + 2개의 수 중 3개를 선택한 경우의 수]  = 1

 

3개의 수 중 2개를 선택하는 경우의 수는

[2개의 수 중 1개를 선택한 경우의 수 + 2개의 수 중 2개를 선택한 경우의 수] = 3

 

3개의 수 중 1개를 선택하는 경우의 수는

[2개의 수 중 0개를 선택한 경우의 수 + 2개의 수 중 1개를 선택한 경우의 수]  = 3

---

 

위 점화식을 이용하여 문제를 풀제를 풀기 위해서는 우선적으로 배열을 정비해줍니다.

 

5개의 수 중 3개를 선택하는 경우 0 ~ 5를 담는 2차원 배열을 만들어줍니다

int array[6][6] = {
 {1, 0, 0, 0, 0, 0}, // 0개의 수 중 0개를 선택할 경우의 수
 {1, 1, 0, 0, 0, 0}, // 1개의 수 중 0개, 1개를 선택할 경우의 수
 {1, 2, 1, 0, 0, 0}, // 2개의 수 중 0개, 1개, 2개를 선택할 경우의 수
 {1, 3, 0, 1, 0, 0}, // 3개의 수 중 0개, 1개, 3개를 선택할 경우의 수
 {1, 4, 0, 0, 1, 0}, // 4개의 수 중 0개, 1개, 4개를 선택할 경우의 수
 {1, 5, 0, 0, 0, 1} // 5개의 수 중 0개, 1개, 5개를 선택할 경우의 수
}

 

0개를 선택하는 수, 1개를 선택하는 수, 배열에 있는 수 만큼 선택하는 수를 배열에 입력했습니다.

남은 경우의 수를 점화식을 이용해 채워주겠습니다.

 

int array[3][2] = array[2][1] + array[2][2]; // 3

int array[4][2] = array[3][1] + array[3][2]; // 6
int array[4][3] = array[3][2] + array[3][3]; // 4

int array[5][2] = array[4][1] + array[4][2]; // 10
int array[5][3] = array[4][2] + array[4][3]; // 10
int array[5][4] = array[4][3] + array[4][4]; // 5

 

반복문을 이용한다면 이렇게 할 수 있을 것 같습니다

for (int i = 2; i <= N; i++) {
    for (int j = 1; j < i; j++) {
        array[i][j] = array[i-1][j-1] + array[i-1][j];
    }
}

 

 

응용 문제

11050, 11051 이항계수 구하기 (조합론) [Bronze I, Silver II]

 

1010 다리 놓기 (조합론) [Silver V]