백준 2775 부녀회장이 될테야(c++)

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

2775번: 부녀회장이 될테야

비교적 쉬운 문제의 DP 문제입니다. 백준 브론즈1 정도의 난이도입니다. 한창 생각없이 알고리즘 문제 풀 때, 이 문제를 dp로 바라보지 않고, 누적합이라고 생각했는데요. 하지만, 알고리즘을 단원별로 나눠서 풀고 문제를 바라보는 관점에 따라, 어떤 알고리즘으로 풀어야 되는지 알게되고 나서부터는 이 문제를 보자마자 DP를 써야겠다고 생각했습니다. 

<코드>

#include <iostream>

using namespace std;
int dp[15][15];
int main()
{
    int t;
    int k, n; // a층 b호

    cin >> t;

    for (int i = 0; i <= 14; i++)
    {
        dp[i][0] = 0;
        dp[0][i] = i;
    }

    while (t--)
    {
        cin >> k >> n;
        for (int i = 1; i <= k; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            }
        }
        cout << dp[k][n] << '\n';
    }
}

우선적으로 0호에 있는 사람들은 0으로 초기화 해줍니다. (의미 없는 값, 단지 점화식을 쓰기 위해 0으로 초기화.. 왜냐하면 실제로 아파트에 0호가 존재하지 않기 때문입니다)

그리고 0호에 i층에 사는 사람들은 i로 초기화 해줍니다. (문제에서 주어진 값을 활용)

이제 점화식을 세워야 합니다. 예시를 들어 2층 3호에 살고 있는 사람 수는 2층 2호에 살고 있는 사람의 수(1층 1호 + 1층 2호), 1층 3호에 살고 있는 사람의 수의 합과 같습니다.  

i=2 , j=3

dp[i][j]  = dp[i][j-1] + dp[i-1][j]

로 식을 세울 수 있습니다.