[C++] 백준 2407 - 조합

백준 2407 : 조합
난이도 : 실버 3
시간 : 30분 소요

문제

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

2407번: 조합

 

 

풀이 방법

이 문제에서는 2가지만 고려하면 된다.

 

1. 이항 계수의 성질

2. long long을 넘는 큰 숫자 다루기

3. 메모이제이션

 

 

이항 계수의 성질

이항계수의 성질 중 파스칼의 삼각형이 있다.

삼각형의 각 항은 위의 두 항을 더한 값이다. 예를 들어, 다음과 같은 파스칼의 삼각형이 있다.

    1
   1 1
  1 2 1
 1 3 3 1
1 4 6 4 1

여기서 4C2 는 6이 된다.

 

이 파스칼 삼각형을 일반화하여 점화식을 유도하면 아래와 같다.

n C m = (n-1) C m + (n-1)C(m-1)
   n == m  -> nCm = 1
   m == 0  -> nCm = 1

예를 들어 100C6 을 구할 때는 아래와 같이 재귀적으로 하여 n과 m이 같아지거나 m == 0 일 때까지 구하면 된다.

100 C 6 = 99C6 + 99C5
  99C6 = 98C6 + 98C5
  99C5 = 98C5 + 98C4
...

 

 

long long을 넘는 큰 숫자 다루기

하지만 값이 매우 커지기 때문에 long long 범위를 벗어나게 된다.

그래서 무척 큰 숫자를 다루기 위해서 string을 사용한다.

 

 

메모이제이션

재귀함수의 문제점인 똑같은 값을 또 구하는 과정을 없애기 위해 이미 구한 값은 바로 리턴해주도록 한다.

무척 큰 숫자를 다루기 위해 string을 사용하기로 했으므로, 아래와 같이 선언해준다.

 

string arr[101][101];

 

ex) arr[5][3] == 5C3의 계산결과를 string으로 나타낸 것이다.

 

 

메모이제이션 설명은 아래에서 자세히 다룬다.

2023.03.13 - [Algorithms] - 메모이제이션(Memoization)과 탭레이션(Tabulation)의 차이

메모이제이션(Memoization)과 탭레이션(Tabulation)의 차이

 

 

최종 코드

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

#define MAX 101

using namespace::std;

int N,M;

string arr[MAX][MAX];

string addCon(string s1, string s2){
    string num = "";
    
    int sum = 0;
    int size = max(s1.size(),s2.size());

    for(int i=0; i<size || sum;i++){   // || sum은 마지막 지릿수 올림일 경우 생각
        if(s1.size()>i) sum += s1[i]-'0';
        if(s2.size()>i) sum += s2[i]-'0';

        num += sum%10 +'0';
        sum /= 10;
    }

        return num;
}

string conbi(int n, int m){
    
    if(n == m || m == 0){
        return "1";
    }
 
    if(arr[n][m] != ""){
        return arr[n][m];
    }
    
    arr[n][m] = addCon(conbi(n-1, m),conbi(n-1, m-1));
    
    return arr[n][m];
    
}

int main(){
    scanf("%d %d", &N, &M);
    
    conbi(N,M);
    
    for(int i=arr[N][M].size()-1; i>=0; i--)
            cout << arr[N][M][i];
    
    cout << '\n';
    
}

 

long long 넘는 큰 숫자를 고려하지 못해 처음엔 틀렸다.