[Baekjoon] Class2 18 - 부녀회장이 될테야 [2775]

부녀회장이 될테야 [2775번]

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

입력

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

출력

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

생각해볼점

0층은 방 번호만큼의 인원수가 채워지고, 이후 층들은 1명씩 채워지는 1번방을 제외하고는 모두 윗층의 같은 번호 방의 인원수 + 같은 층 전 번호 방의 인원수가 현재 방의 인원수가 된다.
따라서 해당 규칙으로 배열을 채우면 된다.

코드 구현

int	main()
{
	int	test_num, floor, room, **arr, temp_floor, temp_room;
	
	scanf("%d", &test_num);

	while(test_num-- > 0)
	{
		scanf("%d %d", &floor, &room);
		arr = (int **)malloc((floor + 1) * sizeof(int *));

		temp_floor = -1;
		while (++temp_floor <= floor)
		{
			arr[temp_floor] = (int *)malloc((room + 1) * sizeof(int));

			if (temp_floor == 0) // 0층의 경우 따로 채워줌
			{
				temp_room = -1;
				while (++temp_room <= room)
					arr[temp_floor][temp_room] = temp_room;
			}
			else // 1층 이후의 경우
			{
				arr[temp_floor][1] = 1; // 첫번째 방만 한명으로 채우고
				temp_room = 1;
				while (++temp_room <= room) // 나머지 방들은 규칙으로 채움
					arr[temp_floor][temp_room] = arr[temp_floor - 1][temp_room] + arr[temp_floor][temp_room - 1];
			}
		}
		printf("%d\n", arr[floor][room]);
		
		temp_floor = -1;
		while (++temp_floor <= floor)
			free(arr[temp_floor]);
		free(arr);
	}
	return (0);
}