[C언어] 백준 2275 부녀회장이 될테야

평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다.
이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다.
아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.

도저히 배열+for문 조합을 쓰지 않고 푸는 방법을 모르겠어서 그냥 풀기로 함.

테스트케이스를 입력받아 그 수만큼 같은 과정을 반복한다.

또한 k와 n의 최대값이 14로 14 * 14 2차원 배열로 그다지 크지 않은 만큼, 그냥 배열 하나를 쭉 채워 놓고 값을 꺼내 출력하는 사람이 많은 듯 했다.

1	1	2	3	4	5	6	7	8	9	10
2	1	3	6	10	15	21	28	36	45	55
3	1	4	10	20	35	46	74	110	155	210
4	1	5	15	25	60	106	180	290	445	655

이차원 배열로 보면 다음과 같은 패턴을 발견할 수 있다.

arr[k][n] = arr[k-1][n] + arr[k][n-1]

예를 들어 3행 3열 값 10 = 2행 3열 값 6 +3행 2열의 값 4이다.

 

그러나 계산 과정에서 필요한 값은 업뎃 이전의 i번째 값과 업뎃 이후 i-1번째 값이기 때문에 1차원 배열로 처리 가능하다.

1열의 값은 변함없이 1이기 때문에 두번째 for문에서 i=0이 아닌 1로 시작하여 nEach[i-1]을 쓸 수 있다.

#include <stdio.h>

int main(void)
{
	int T, k, n, i;
	int nEach[14] = { 0 };

	scanf("%d", &T);

	while (T--)
	{
		scanf("%d %d", &k, &n);

		for (i=0; i < n; i++) //1열의 값 1,2,3,4,5, ... 초기화
			nEach[i] = i + 1;
		while(k--)
			for(i=1; i < n; i++)
				nEach[i] += nEach[i-1];

		printf("%d\n", nEach[n-1]);
	}

	return 0;
}