백준 02407 - 조합

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

2407번: 조합

 

고려사항

• long long 을 넘어가는 수 출력. ( 문자열로 다루는 것도 생각해보았지만 너무 복잡, 실패...다른 해결법을 참조하였다..)
• 조합은 이항 계수 공식 사용. ( 수학을 못하는 문돌이 출신은 이번에 처음 알았다..ㅎㅎ )
• 100C50 이 대략 10^29 ~ 10^30 사이의 수이다.
• 10^15 를 maxValue 로 정해놓고, 이 값 이상이면, carry 배열+1
• 출력은 carry > 0 일 시에, 먼저 carry 출력 후 combi 출력.
  carry 가 존재하고, combi 가 10^13 이하의 수면 자리수를 맞춰 주기 위해 37라인 처럼 출력 해주기.
  그렇지 않으면 만약에 carry와 combi 수 모두 1이면 1000....0001 => 11 로 출력된다.

 

#include <cstdio>
#define maxValue 1000000000000000
using namespace std;
 
long long combi[101][101];
long long carry[101][101];
 
int main(){
    int n, m;
    long long tmp;
 
    scanf("%d %d", &n, &m);
    if(m > n/2){
        m = n-m;
    }
 
    for(int i=1;i<=n;++i){
        for(int j=0;j<=n;++j){
            if(j == 0 || j == i ){
                combi[i][j] = 1;
            }else if(j == 1){
                combi[i][j] = i;
            }else{
                carry[i][j] = carry[i - 1][j] + carry[i - 1][j - 1];
                tmp = combi[i - 1][j] + combi[i - 1][j - 1];
                if(tmp >= maxValue){
                    ++carry[i][j];
                    combi[i][j] = tmp - maxValue;
                }else{
                    combi[i][j] = tmp;
                }
            }
        }
    }
 
    if(carry[n][m] > 0){
        printf("%lld%015lld", carry[n][m], combi[n][m]);
    }else{
        printf("%lld", combi[n][m]);
    }
    return 0;
}