[BOJ/C++] 2775 부녀회장이 될테야

k층의 n호에 사는 사람의 점화식을 구해 문제를 해결할 수 있습니다.

0층의 i호에는 i명의 사람이 살고 있으므로 0층에는

1, 2, 3, 4, ... ,15 명이 각 살고 있습니다.

또한 각 층의 1호에는 a층 b호에는 (a-1)(0) ~ (a-1)(b)호의 사람들이 살고 있으므로 1명이 살고 있습니다

즉 다음과 같은 구조를 가지고 있습니다.

1 ? ? ? ? ...
1, 4, 10, 20 ...
1, 3, 6, 10, ...
1, 2, 3, 4, ...

1층 3호는 6명(3+3), 2층 3호는 10명(4+6)

이 때 $i$층의 $j$호의 사람에 대한 점화식을 구하면 다음과 같습니다.

$DP[i][j] = DP[i-1][j] + DP[i][j-1]$

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>
#include <climits>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>

using namespace std;

using int32 = long;
using int64 = long long;

// main에 선언하면 스택 오버플로우 발생
static int DP[15][15] = { {0} };

int main() {
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cout.tie(nullptr);

   int T;
   cin >> T;


   for(int i=1; i<15; i++)
   {
       DP[0][i] = i;
       DP[i][1] = 1;
   }

   for(int i=1; i<15; i++)
   {
       for (int j = 2; j < 15; j++)
           DP[i][j] = DP[i - 1][j] + DP[i][j - 1];
   }

   for(int i=0; i<T; i++)
   {
       int k, n;
       cin >> k >> n;

       cout << DP[k][n] << '\n';
   }

   
   return 0;
}