백준(BAEKJOON): 부녀회장이 될테야(2775번)

Source

문제

평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다.

이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다.

아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.

입력

첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다. (1 <= k <= 14, 1 <= n <= 14)

출력

각각의 Test case에 대해서 해당 집에 거주민 수를 출력하라.

예제 입력 1

2
1
3
2
3

예제 출력 1

6
10

해설

뭔가 어럽다. 천천히 문제를 읽어 보자.

0:  1   2   3   4   5   6   7   8   9   10  11   12   13   14
------------------------------------------
1:  1   3   6   10  15  21  28  36  45  55  66   78   91   105
2:  1   4   10  20  35  56  84  120 165 220 286 364  455   560
3:  1   5   15  35  ...

아파트라고 하지만 이런 형식의 행렬 혹은 이차원 배열을 생성하라는 문제로 읽힌다. 입력에서 행렬 위치값을 입력받아 그 위치의 값을 출력하는 문제라고 생각하고 코드를 짰다. 수학1로 분류된 문제이니 루프를 돌리지 않고 간단하게 각 배열의 값을 알아낼 수 있는 수식을 찾아야 하는 건지도 모르겠다. 하지만 우선은 떠오르는 대로....

먼저 위의 배열을 만들어 보자.

    int apart[15][15] = { {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }, };
    int i, j, sum;

    for (i = 1; i < 15; ++i) {
        sum = 0;
        for (j = 1; j < 15; ++j) {
            sum += apart[i-1][j];
            apart[i][j] = sum;
        }
    }

이차원 배열 apart[15][15]를 생성한다. 그런데 행렬의 값을 채우기 위한 기본값이 문제에서 제시되었으므로 이 값을 반영하여 배열을 초기화한 것이다. 즉 0층의 i호에는 i명이 살고 있으므로 int apart[15][15] = { {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }, };로 초기화한다. 이 0층의 인원을 토대로 1~14층까지의 인원을 계산하여 각 호의 값으로 지정한 것이다.
테이블이 완성되었으므로 테스트 게이스의 개수와 행과 열 값을 입력받아 배열의 해당 위치의 값을 출력해준다.

소스코드: C

#include <stdio.h>
int main(int argc, char *argv[])
{
    int apart[15][15] = { {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }, };
    int i, j, sum;
    int test_case, floor, number;

    for (i = 1; i < 15; ++i) {
        sum = 0;
        for (j = 1; j < 15; ++j) {
            sum += apart[i-1][j];
            apart[i][j] = sum;
        }
    }

    scanf("%d", &test_case);
    for (i = 0; i < test_case; ++i) {
        scanf("%d", &floor);
        scanf("%d", &number);
        printf("%d\n", apart[floor][number]);
    }
    return 0;
}