[알고리즘] 백준 2775번 "부녀회장이 될테야" 문제 풀이 (C/C++) - Don 임베디드

한 복층의 아파트가 있다.

아파트 각 호수에 사는 사람의 수에는 규칙이 존재한다.

[규칙 1] "a층의 b 호에 사는 사람의 수는

            자신의 아래 (a-1) 층 1호 부터 b호 까지

            사는 사람들의 수를 더한 만큼이다."

[규칙 2] "층수는 0층~14층 까지 있으며,

            호수는 1호~ 14호 까지 있다."

[규칙 3] "아파트 0층 각 i호 에는 i명의 사람이 살고 있다."

[규칙 4] "아파트에 비어있는 집은 없고,

            모든 거주민들이 위 규칙을 지키고 있다."

 

첫째 줄에 Test Case의 수 T가 주어진다.

각 Test Case 마다 입력으로 정수 k(층 수), n (호수)가 주어진다.

각 Test Case에 대해서 해당 집에 거주하는 사람의 수를 구하라.

 

제약:

제한 시간 1초, 메모리 128MB

(1 <= k, n <= 14)

 

예제 1 입력.	예제 1 출력.
2 1 3 2 3	6 10

 

 

#include <iostream>
 
using namespace std;
 
int main()
{
    int T, k, i;
    int nNumOfPeople[15][15];
 
    // 규칙에 따라 모든 층, 호수에 해당하는 사람 수 계산. (범위가 작기 때문에 가능)
    for (int floor = 0; floor <= 14; floor++)
    {
        for (int unit = 1; unit <= 14; unit++)
        {
            if (floor > 0)
            {
                if (unit > 1)
                {
                    nNumOfPeople[floor][unit] = nNumOfPeople[floor][unit - 1] + nNumOfPeople[floor - 1][unit];
                }
                else
                {
                    nNumOfPeople[floor][unit] = nNumOfPeople[floor - 1][unit];
                }
            }
            else
            {
                nNumOfPeople[floor][unit] = unit;
            }
        }
    }
 
    // TC 개수 입력.
    cin >> T;
 
    while (T-- > 0)
    {
        // 층, 호수 입력.
        cin >> k >> i;
        // 계산한 값 바로 출력.
        cout << nNumOfPeople[k][i] << endl;
    }
    return 0;
}

문제 원본 링크:

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