[백준 11050] 이항계수 1 (반복, 재귀)

• 안녕하세요. BlockDMask 입니다.

• 비가 추적추적 내리는 월요일이네요. 오늘의 문제를 포스팅 해보겠습니다.

0. 제목

• BOJ 11050 이항계수 1

• 백준 11050 이항계수 1 

• C++ 이용해서 풀었습니다.

1. 문제 설명

자연수 N과 정수 K가 주어졌을때, 이항계수  

를 구하는 문제입니다.

2. 풀이 과정

이항계수( binomial coefficient ) 는 경우의 수를 계산할때 사용하는 것으로 알고있습니다.

n개의 서로다른 것 들 중에서 k 개를 선택하는 것의 조합(combination)의 경우의 수를 구하는 것입니다.

는

로 나타내고 이는

으로 나타낼 수 있습니다.

팩토리얼(Factorial)은 반복문과 재귀 두가지 방법으로 표현 할 수 있기 때문에

두가지 방법 모두를 사용하여 풀어보았습니다.

3. 함수 설명

T1) 반복문에서의 Factorial 함수

num을 인자로 받아서,

반복문을 통해 num * num-1 * num-2 * . . . . . . . .* 1 을 구합니다.

T2) 재귀함수에서의 Factorial 함수

num을 인자로 받습니다.

재귀 함수에서는 순환부와 종료부로 이루어져있어야하는데, 

종료부는 num이 1 또는 0 인 경우 return 1을 합니다.

그렇지 않으면 순환부로 넘어가서

return Factorial(num-1) * num; 으로 호출하게됩니다.

ex) num이 3일때 재귀함수의 흐름을 보겠습니다.

num = 3; -> 순환부로 갑니다.

return Factorial( 3 - 1 ) * 3;

num = 2; -> 순환부로 갑니다.

return Factorial( 2 - 1 ) * 2;

num = 1; -> 종료부로 갑니다.

return 1;

이제 다시 역순으로 올라가게 되면,

num =1 일때 return 이 1이므로 Factorial (2-1) 의 값은 1 입니다.

num = 2 일때 return 이 1 * 2 이 되므로 Factorial (3-1) 값은 2 입니다.

num = 3일때 resutrn 이 2 * 3 이 되므로

3! = Factorical(3) = 6 이 됩니다.

4. 코드

T1) 반복문을 이용한 이항계수 구하기

#include<iostream>
 
using namespace std;
 
//반복문 이용. 
int Factorial(int num){
    if(num == 0) return 1;
    
    int result = 1;
    
    for(int i=num; i>=1 ; i--){
        result *= i;
    }
 
    return result;
}
 
 
int main(void){
    
    int n, k;
 
    cin >> n >> k;
 
    cout << Factorial(n) / (Factorial(k) * Factorial(n-k));
    
    return 0;    
}

T2) 재귀함수를 이용한 이항계수 구하기

#include<iostream>
 
using namespace std;
 
//재귀 이용.
int Factorial(int num){
    if(num == 1 || num == 0){
        return 1;
        
    }else{
        return Factorial(num-1) * num;
    }
 
}
 
int main(void){
    
    int n, k;
 
    cin >> n >> k;
 
    cout << Factorial(n) / (Factorial(k) * Factorial(n-k));
    
    return 0;    
}

5. 인증

T1) 반복문 이용

T2) 재귀 함수 이용

출처 : https://www.acmicpc.net/problem/11050

읽어주셔서 감사합니다.