[백준] 11050 & 11051 이항계수 구하기 (c++)

조합 점화식 

D[i][j] = D[i-1][j] + D[i-1][j-1]

 

---

11050 이항 계수 1

 

• 조합의 정의를 이용, 팩토리얼 함수를 이용해서 풀기 

#include <iostream>
using namespace std;

int factorial(int t) {
    int ans = 1;
    for(int i = t; i > 0; i--) {
        ans *= i;
    }
    return ans;
}

int main() {
    int N, K, result;
    cin >> N >> K;

    result = factorial(N) / (factorial(N-K) * factorial(K));

    cout << result << '\n';
}

이 문제에서는 N과 K 의 값이 10 이하이기 때문에 문제없이 돌아감. 

• factorial(N), factorial(K), factorial(N-K)을 각각 별도로 계산하고 있는데, 이 과정에서 중복된 연산이 발생. 예를 들어 factorial(N)을 계산할 때 factorial(N-K)까지의 값을 이미 계산하게 됨. 하지만 그 계산 결과를 따로 저장하지 않고 다시 처음부터 factorial(N-K)와 factorial(K)을 각각 계산하기 때문에 같은 값을 여러 번 계산하는 비효율이 발생

 

• 점화식을 이용해서 풀기 

#include <stdio.h>
#include <iostream>
using namespace std;

int main()
{
   int N, K;
   cin >> N >> K;
   
   int D[11][11];
   
   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];
       }
   }
   
   cout << D[N][K] << "\n"; 
}

• 앞선 중복값 계산 비효율을 해결할 수 있다. 

 

11051 이항 계수 2

• 11050 문제와 거의 유사하고, N,K 의 최대값과 나머지를 구한다는 사실만 다름 
•  단순히 11050 의 코드에 N,K 값 상한을 조정하고 결과값에서 모듈러 연산을 사용하면 런타임 에러(IntegerOverflow) 가 뜬다. 

#include <stdio.h>
#include <iostream>
using namespace std;

int main()
{
   int N;
   int K;
   
   cin >> N >> K;
   
   int D[1001][1001];
   
   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];
           D[i][j] = D[i][j] % 10007; 
       }
   }
   
    cout << D[N][K] << "\n";
}

• 이렇게 점화식을 사용, 반복문 안에서 모듈러 연산을 수행하면 숫자가 너무 커지는 것을 방지해서 런타임 에러를 피할 수 있음

이항 계수와 모듈러 연산 

• 모듈러 연산의 성질 : 모듈러 연산은 덧셈, 뺄셈, 곱셈에서 분배 법칙이 적용

• 이항 계수 구하기(조합 구하기) : D[i][j] = D[i-1][j] + D[i-1][j-1] 점화식을 이용함 

점화식을 수식으로 나타냄

 

• 점화식에 모듈러 연산의 성질을 사용한다고 할 때, 중간에 모듈러 연산을 진행해도 결과값(나머지)는 바뀌지 않음 

 

---

런타임 에러(IntegerOverflow) 

정수(int) 가 저장할 수 있는 가장 큰 값(2147483647) 보다 더 큰 값, 또는 가장 작은 값(-2147483648) 보다 더 작은 값을 저장하려고 할 때 발생

 

• 11051 에서 factorial(20) 이 벌써 2,432,902,008,176,640,000 이기 때문에 당연히 오버플로우가 발생한다.