[Algorithm] Baekjoon 2407번 : 조합

https://www.acmicpc.net/problem/2407

2407번: 조합

 

string dp[106][106]; // 뒤집어서 저장되어있음.
 
string Add(string a, string b) // 각 수는 뒤집혀서 들어옴.
{
    string result = "";
    int sum = 0;
    
    int maxSize = max(a.size(), b.size());
    int aSize = a.size();
    int bSize = b.size();
    int index = 0;
 
    while (1)
    {
        if (index < aSize)
        {
            sum += a[index] - '0';
        }
 
        if (index < bSize)
        {
            sum += b[index] - '0';
        }
 
        result.push_back((sum % 10) + '0');
        sum = sum / 10;
        index++;
        if (sum == 0 && index >= maxSize) break;
    }
    
    return result;
}
 
string Combination(int n, int m)
{
    if (m == 0 || n == m) return "1";
    
    string& str = dp[n][m];
    if (str != "") return str;
 
    str = Add(Combination(n - 1, m - 1), Combination(n - 1, m));
 
    return str;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
    int m = 0;
 
    cin >> n >> m;
 
    string result = Combination(n, m);
    reverse(result.begin(), result.end());
 
    cout << result << endl;
}

문제자체는 매우 심플하다. nCm 구하는 문제.

기본공식은 nCm = n! / r!(n-r)! 으로, 굉장히 쉬워보이지만 실제로 팩토리얼 계산하려하면 터진다.

20!만해도 단위가 unsigned long long 이랑 비슷해진다.

당연히 팩토리얼로 계산하면 안되고, nCm에는 또다른 규칙이 존재한다.

 

nCm = n-1Cm-1 + n-1Cm    

nCn == 1 , nC0 == 1. 

 

재귀방식으로 풀어야하며, 당연히 한번 풀었던 값에대해서는 기록을 해놔야 스택메모리가 안터진다.

dp문제라고도 볼 수 있다.

 

값이 매우 크기 때문에 string으로 계산해서 풀어야 한다.

나같은 경우 Add를 호출할때마다 reverse를 하는것도 비용이 크다고 생각해서 reverse를 호출 안하게 구현해봤다.

Add의 두 매개변수는 뒤집혀서 들어온다고 가정하고 코드를 짰다.

예전에 비슷한 문제 풀때는 더 하드코딩식으로 짰던거 같은데, 앞으로는 저렇게 코드를 짤 거 같다.

개인적인 생각이지만 아마 저렇게 짜면 타임아웃이 나진 않을거다.

 

문제를 풀면 풀수록, 내가 코테에서 왜 떨어졌는지 너무 잘 알게된다..