백준 2407번 조합 C언어 풀이

그냥 조합 구하는 식으로 계속 곱해주면 100C50이 감당이안된다(30자리)
그래서 long long 의 범위를 넘는 값이 출력된다고 하면,
새로운 배열에 입력해서 출력할때 나눠서 해줄거다.

두번째로는 조합의 성질 nCr = n-1Cr + n-1Cr-1의 성질을 이용하여
nC0부터 메모제이션을 이용하여 하나씩 값을 올려줬다.
설명은 이정도만보고 코드를 보고이해하자 훨씬 빠를거다.

#include <stdio.h>

long long arr[101][101][2];  // longlong 의 범위 –9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 (19자리)

int main() {
    int n, m;
    int i, j;
    scanf("%d %d", &n, &m);

    for (i = 1; i <= n; i++) {      // nCm 의 n memozation
        for (j = 0; j <= i; j++) {  // nCm 의 m
            if (j == 0 || j == i)
                arr[i][j][0] = 1; /**arr[n][m][0]만 해주는이유는 arr[n][m][1]은 100C50의 값이 30자리기때문에
18자리정도에서 컷트시켜주고 그이후부터 arr[n][m][1] 건드릴거임**/
            else {
                arr[i][j][0] = arr[i - 1][j - 1][0] + arr[i - 1][j][0];
                arr[i][j][1] = arr[i - 1][j - 1][1] + arr[i - 1][j][1];
            }
            if (arr[i][j][0] >= 100000000000000000) {
                arr[i][j][1]++;                      // 17의자리 수 부터는 여기에 저장
                arr[i][j][0] %= 100000000000000000;  // 맨 앞자리 날려주고 그앞자리는 arr[i][j][1]에 더해줌
            }
        }
    }
    if (arr[n][m][1] == 0)
        printf("%lld", arr[n][m][0]);
    else
        printf("%lld%lld", arr[n][m][1], arr[n][m][0]);
}

1192052400](https://www.acmicpc.net/problem/2407)