백준_2775_부녀회장이될테야

 

규칙이 있는 아파트 문제입니다.

 

a층의 b 호에 살기 위해서는 a-1층의 1호~b호 까지의 사람의 합 만큼 사람을 데려와야 한다는 규칙이 있습니다.

 

처음에는 반복문을 통해 시그마를 구현하고 하나하나 다 더해서 풀어야 하나 생각을 했지만 더 간단한 방법이 있었습니다.

 

아파트를 표로 구현해보았습니다.

아래 표에서 규칙을 찾으면, 문제를 쉽게 풀 수 있을 것 같습니다.

2층	1명	4명	10명	20명	35명	56명	84명	120명	165명
1층	1명	3명	6명	10명	15명	21명	28명	36명	45명
0층	1명	2명	3명	4명	5명	6명	7명	8명	9명
	__1호	__2호	__3호	__4호	__5호	__6호	__7호	__8호	__9호

 

규칙이 보이시나요??

 

해당 호수에 몇명이 살고 있는지 구하기 위해서는, 같은 층의 이전 호수와, 바로 아래층의 같은 호수에 살고 있는 사람 수를 더하면 됩니다.

 

위의 표를 2차원 배열 apt[14][14] 라고 한다면 , apt[i][j] = apt[i-1][j] + apt[i][j-1] 이 되겠죠.

 

배열의 크기를 14x14 로 한 이유는 문제에서 범위를 정해주었기 때문입니다. 

 

이를 코드로 구현해보면 다음과 같습니다.

 

먼저 __1 호의 사람수는 항상 1명이므로, 1로 초기화를 해주고 

0층에 사는 사람의 명수까지 초기화해주었습니다.

 

그 후 위의 규칙을 통해 사람 수를 배열에 채워 넣는 과정입니다.

    int apt[15][15] = {0}; // 아파트 배열

    for (int i = 0; i < 15; i++)
    {
        apt[0][i] = i + 1;
        apt[i][0] = 1;
    }

    for (int i = 1; i < 15; i++)
    {
        for (int j = 1; j < 15; j++)
        {
            apt[i][j] = apt[i - 1][j] + apt[i][j - 1];
        }
    }

 

 

이 과정이 끝나면, 호수를 입력받아 사람 수를 출력만 하면 문제를 해결할 수 있겠죠.

 

 

전체 코드)

#include <stdio.h>

int main(void)
{
    int apt[15][15] = {0}; // 아파트 배열

    for (int i = 0; i < 15; i++)
    {
        apt[0][i] = i + 1;
        apt[i][0] = 1;
    }

    for (int i = 1; i < 15; i++)
    {
        for (int j = 1; j < 15; j++)
        {
            apt[i][j] = apt[i - 1][j] + apt[i][j - 1];
        }
    }

    int T, k, n;

    scanf("%d", &T);

    for (int i = 0; i < T; i++)
    {
        scanf("%d\n%d", &k, &n);
        printf("%d\n", apt[k][n - 1]);
    }

    return 0;
}

 

 

규칙만 파악하면 어렵지 않게 풀 수 있는 문제인 것 같습니다.