[알고리즘 풀이 분석] BOJ 2407 조합

2일 전 풀어본 문제를 까먹고 있다가 복습해본다!
풀었던 문제는 BOJ 2407 조합 이다. 간단한 DP 문제인데 늘 같은 방식으로 구현하던 조합을 DP를 이용해 새로운 방법으로 구하는 방법을 배울 수 있었다.

BOJ 2407 조합

nCm을 출력한다.

입출력

[입력]
n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)

[출력]
nCm을 출력한다.

풀이

처음엔 우리가 고등학교 시절부터 흔히 사용하고 있는 조합 공식을 이용해서 풀려고 하였다. 1~m 까지 nC1 을 이용해 nC2, nC2 를 이용해 nC3 ... 과 같은 방식으로 dp를 사용하는 알고리즘을 세웠다.

하지만 문제의 입출력 범위에서 문제가 있었다. n 과 m이 각각 100,50 인 경우 굉장히 큰 값이 나오는데 이는 long long 형을 사용해도 감당 할 수 없는 크기의 수이다. 이전 결과를 먼저 나누고 이후 곱하는 방식으로도 해 봤지만 계속 "틀렸습니다" 를 만났고 아무래도 자료형이 그 값을 감당하지 못해 수가 잘려서 인 것 같았다.

보편적인 조합 공식을 사용해서는 그 범위를 감당할 수 없을 것 같아 다른 분의 풀이 포스팅을 참고해 해결할 수 있었다.

해결법은 정수형이 아닌 string 자료형을 사용하는 것이었다.

먼저 파스칼의 삼각형 방식 nCr = n-1Cr-1 + n-1Cr 을 이용해 조합을 재귀적으로 구해 나가고 그 결과를 담는 방식을 정수형이 아닌 문자열 형식으로 바꿔주어야 한다.

예를 들어 nCr = n-1Cr-1 + nCr-1 을 이용해 3C2 를 구한다고 하면, 3C2 = 2C1 + 2C2 = 2 + 1 이다. 이 때 "2" + "1" 을 통해 문자열 "3" 을 구할 수 있도록 하는 것이다.

주어진 두 문자열을 가장 뒷자리 부터 정수로 변환해 더해간다. 더한 값이 10을 넘는다면 그 나머지 값은 문자열로 변환해 결과 값으로 합쳐주고 10으로 나눈 몫은 다시 다음 자리 문자열 더하는데에 반영한다.

만약 "24" + "37" 을 연산해 결과 문자열 result 를 얻으려 한다면 "4" 와 "7" 을 더해 11 이 되고 이 중 10으로 나눈 나머지 값 1은 먼저 결과 result 에 반영되어 result = "1", 11을 10으로 나눈 몫 1은 다시 다음 연산에 반영되어 "1" + "2" + "3" = "5" 가 되는 것이다. 5는 10을 넘지 않으므로 바로 결과 문자열에 반영되어 result = "5"+"1" = "51" 이 된다.

재귀적으로 조합을 구해 나가는 과정에서 이미 구해 놓은 값이 있다면 DP를 통해 반영할 수 있도록 2차원 배열에 해당 값을 담아두고 사용하는 방식으로 진행하면 파스칼의 삼각형을 이용해 DP 방식으로 조합을 구할 수 있다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

//boj 2407 조합, dp, 실버 3
using namespace std;

string dp[101][101];

string makeStringSum(string a, string b){  // 두 문자열을 더하기 
    int sum = 0;
    string answer = "";

    while (!a.empty() || !b.empty() || sum!=0) {
        if (!a.empty()){
            sum += a.back()-'0';
            a.pop_back();
        }

        if (!b.empty()){
            sum += b.back()-'0';
            b.pop_back();
        }

        answer.push_back((sum%10)+'0');
        sum = sum/10;
    }

    reverse(answer.begin(), answer.end()); // 뒤쪽부터 더해 나간 문자열 거꾸로 돌리기 
    return answer;
}

string combination(int n, int r){
    if (n==r || r==0) return "1";
    if (dp[n][r] != "") return dp[n][r];  // DP 

    dp[n][r] = makeStringSum(combination(n-1, r-1), combination(n-1, r));  // 파스칼의 삼각형 이용, 재귀 

    return dp[n][r];
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, M;
    cin>>N>>M;

    cout<<combination(N, M);

    return 0;
}

Reference

[백준] 2407번 조합 - C++