[BAEKJOON] 2775번

각 아파트에 사는 사람을 표로 표현하면 다음과 같다.

1	16	136	…
1	15	120
1	14	105
1	13	91
1	12	78
1	11	66
1	10	55
1	9	45
1	8	36
1	7	28
1	6	21
1	5	15
1	4	10	20	35	56	81	107	152	207	273	351	442	547
1	3	6	10	15	21	28	36	45	55	66	78	91	105
1	2	3	4	5	6	7	8	9	10	11	12	13	14

첫번째 열을 제외하고 대각선 대칭이다.

3-3

4-6-4

5-10-10-5

6-15-20-15-6

7-21-35-35-21-7

...

따라서 n행 n열의 값은 n-1행 n열과 n행n-1열의 값의 합이다.

#include <stdio.h>
 
#define HOUSES 14
#define FLOORS 15
 
int main()
{
    int apart[FLOORS][HOUSES];
    int t, i, j;
    int k, n;
 
    /*initialize*/
    for (i = FLOORS - 1; i >= 0; --i) apart[i][0] = 1;
    for (j = 1; j < HOUSES; ++j) apart[FLOORS - 1][j] = (j + 1);
    for (i = FLOORS -2; i >= 0; --i)
    {
        for (j = 1; j < HOUSES; ++j)
        {
            apart[i][j] = apart[i + 1][j] + apart[i][j - 1];
        }
    }
 
    scanf("%d", &t);
    for (; t > 0; --t)
    {
        scanf("%d", &k);
        scanf("%d", &n);
 
        printf("%d\n", apart[FLOORS - 1 - k][n - 1]);
    }
 
    return 0;
}

모든 호실에 각각 그 호실에 사는 사람의 수를 저장해 테이블을 형성하고

입력받은 층과 호수에 맞춰 테이블에서 읽어온다.