[백준/c++] 2407번 조합

2407번 문제 링크

문제

nCm을 출력한다.

입력

n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)

출력

nCm을 출력한다.

풀이

이 문제에서 가장 유의해야할 부분은 바로 자료형 범위다. c++ 의 자료형은 다음과 같다.

자료형	범위
(signed) int	-2,147,483,648 ~ 2,147,483,647
unsigned int	0 ~ 4,294,967,295
(signed) long (int)	-2,147,483,648 ~ 2,147,483,647
unsigned long (int)	0 ~ 4,294,967,295

범위가 가장 크더라도 정수형인 경우 4,294,967,295 까지만 가능한데 n 과 m 이 100 까지 입력가능하기 때문에 4,294,967,295 는 넘을 수 밖에 없다. 그렇기 때문에 값의 자료형을 문자열로 취급한다

그리고 조합 데이터 구하는 로직은 파스칼의 삼각형 및 memoization 을 통해서 간소화한다.

관련해서 설명은 아래 글을 참고 👇
[알고리즘] 파스칼의 삼각형
[알고리즘] 동적 계획법 (Dynamic Programming, DP)

소스코드

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int N, M;
string factorial[101][101];

string bigNumAdd(string n1, string n2) {
    int sum = 0;
    string result; //1의 자리부터 더하기
    
    while (n1.empty() == false || n2.empty() == false || sum) {
        if (n1.empty() == false) {
            sum += n1.back() - '0'; n1.pop_back();
        }
        
        if (n2.empty() == false) {
            sum += n2.back() - '0';
            n2.pop_back();
        }
        
        result.push_back((sum % 10) + '0');
        sum /= 10;
        
    } //역순이므로 다시 역순
    
    reverse(result.begin(), result.end());
    return result;
}

string combination(int n, int r) {
    if (n==r || r==0) return "1";
    
    string &result = factorial[n][r]; // 참조형 변수
    
    //memoization
    if (result != "") return result;
    
    //파스칼삼각형
    result = bigNumAdd(combination(n-1, r-1), combination(n-1, r)); return result;
    
}

int main() {
    cin >> N >> M;
    cout << combination(N, M);
}

정답