코드

#include <iostream>
#include <string.h>
#include <algorithm>

using namespace std;
string a[101][101];

string calStr(string a, string b)
{
    int alen = a.length();
    int blen = b.length();
    int clen = max(alen, blen) + 1;
    string c = "";
    for (int i = 0; i < clen; i++)
    {
        c += "0";
    }
    int i = alen - 1;
    int j = blen - 1;
    int k = clen - 1;

    while (i >= 0 && j >= 0)
    {
        int num = a[i] - '0' + b[j] - '0';

        int tenth = num / 10;
        int first = num % 10;
        //  cout << tenth << " " << first << "\n";
        c[k] = c[k] - '0' + first + '0';
        if (c[k] - '0' >= 10)
        {
            c[k] = c[k] - 10;
            c[k - 1] += 1;
        }
        c[k - 1] = c[k - 1] - '0' + tenth + '0';
        if (c[k - 1] - '0' >= 10)
        {
            c[k - 1] = c[k - 1] - 10;
            c[k - 2] += 1;
        }
        k--;
        i--;
        j--;
    }

    while (i >= 0)
    {
        int num = a[i] - '0';
        int tenth = num / 10;
        int first = num % 10;
        c[k] = c[k] - '0' + first + '0';
        c[k - 1] = c[k - 1] - '0' + tenth + '0';
        i--;
        k--;
    }

    while (j >= 0)
    {
        int num = b[j] - '0';
        int tenth = num / 10;
        int first = num % 10;
        c[k] = c[k] - '0' + first + '0';
        c[k - 1] = c[k - 1] - '0' + tenth + '0';
        j--;
        k--;
    }

    for (i = 0; i < clen; i++)
    {
        if (c[i] != '0')
            break;
    }
    string d = c.substr(i, clen);
    /*
        cout << d << " "
             << "a : " << a << " "
             << "b : " << b << "\n";
    */
    return d;
}
int main(void)
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            a[i][j] = "0";
        }
    }
    for (int i = 0; i <= n; i++)
    {
        a[i][0] = "1";
        a[i][i] = "1";
    }
    //  cout << calStr("11628", "3876");

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            // cout << "i : " << i << "j : " << j << "\n";
            a[i][j] = calStr(a[i - 1][j - 1], a[i - 1][j]);
        }
    }

    cout << a[n][m];

    return 0;
}

문제 접근

다이나믹 프로그래밍

메모리 제이션을 이용하여, 계산 속도를 최적화 해야한다.

조합

서로다른 n개에서 r개를 순서 상관없이 선택하는 경우의 수

해결 방법

파스칼의 삼각형

https://ko.wikipedia.org/wiki/%ED%8C%8C%EC%8A%A4%EC%B9%BC%EC%9D%98_%EC%82%BC%EA%B0%81%ED%98%95

기억 해야 할 것

• 팩토리얼을 구해야하므로, 딱봐도 자릿수의 문제가 생길거 같음 -> String 으로 생각해 주어야 함.
• 파스칼의 삼각형,,, 기억하자,,