[백준] 부녀회장이 될테야 (C++)

 

문제 URL:

www.acmicpc.net/problem/2775

2775번: 부녀회장이 될테야

 

다음 문제는 

"a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다"는

규칙이 있어서 이를 만족하기 위해 일단 2차원 배열을 만들어 각각의 요소에 해당하는 값을 넣어주었다.

 

먼저 층을 행, 호를 열로 생각(0층을 포함하여)하여 15x14인 2차원 배열을 선언하고,

0층은 i호에 i명이 거주하므로 0행 1~14호(0~13열)에 1~14까지의 숫자를 대입하였다.

또한 각 층의 1호(0열)에는 1명만 거주 가능하므로 0열의 각 행에 모두 1을 대입하였다.

 

그 뒤 위 규칙에 따르면 a층의 b호 거주민 수는 (a-1층 b호 거주민 수) + (a층 b-1호 거주민 수)이므로 이를 이용하여 문제를 풀었다.

---

#include<iostream>
using namespace std;

int f(int k, int n)
{
    int matrix[15][14];

    for (int j = 0; j < 14; j++)
        matrix[0][j] = j + 1;
        
    for (int j = 0; j < 14; j++)
        for (int i = 1; i < 15; i++)
        {
            if (j == 0)
                matrix[i][j] = 1;
            else
                matrix[i][j] = matrix[i - 1][j] + matrix[i][j - 1];
        }

    return matrix[k][n];
}

int main()
{
    int t, k, n;
    cin >> t;
    for (int i = 0; i < t; i++)
    {
        cin >> k;
        cin >> n;
        cout << f(k, n-1) << "\n";
    }
}