백준 2407번 조합

문제 링크입니다: https://www.acmicpc.net/problem/2407

백준 1793번 타일링(http://jaimemin.tistory.com/618)처럼 long long 자료형의 범위를 벗어나는 답을 구해야하기 때문에 string을 통해 Big Integer를 구현합니다.

조합의 경우 간단한 DP를 통해 구할 수 있기 때문에(nCr = n-1Cr + n-1Cr-1) 별도의 설명이 필요가 없습니다.

#include <iostream>

#include <string>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 100 + 1;

 

int N, M;

string cache[MAX][MAX];

 

string bigNumAdd(string num1, string num2)

{

        long long sum = 0;

        string result;

 

        //1의 자리부터 더하기 시작한다

        while (!num1.empty() || !num2.empty() || sum)

        {

                 if (!num1.empty())

                 {

                         sum += num1.back() - '0';

                         num1.pop_back();

                 }

                 if (!num2.empty())

                 {

                         sum += num2.back() - '0';

                         num2.pop_back();

                 }

                 //다시 string 형태로 만들어 push_back

                 result.push_back((sum % 10) + '0');

                 sum /= 10;

        }

        //1의 자리부터 result에 넣었으므로 뒤집어줘야한다

        reverse(result.begin(), result.end());

        return result;

}

 

//nCr = n-1Cr + n-1Cr-1

string combination(int n, int r)

{

        if (n == r || r == 0)

                 return "1";

 

        string &result = cache[n][r];

        if (result != "")

                 return result;

 

        result = bigNumAdd(combination(n - 1, r - 1), combination(n - 1, r));

        return result;

}

 

int main(void)

{

        cin >> N >> M;

 

       

        cout << combination(N, M) << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~