(백준) 2775 부녀회장이 될테야 C++

 

1	11	66	286	1001	3003	8008	19448	43758	92378
1	10	55	220	715	2002	5005	11440	24310	48620
1	9	45	165	495	1287	3003	6435	12870	24310
1	8	36	120	330	792	1716	3432	6435	11440
1	7	28	84	210	462	924	1716	3003	5005
1	6	21	56	126	252	462	792	1287	2002
1	5	15	35	70	126	210	330	495	715
1	4	10	20	35	56	84	120	165	220
1	3	6	10	15	21	28	36	45	55
1	2	3	4	5	6	7	8	9	10

문제를 표로 나타내보자면 위와 같다.

맨 아래를 0층에선 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.  라고 명시가 되어있다.
이후 부턴 (a-1)층의 n호까지 살고 있는 총합이 구해야할 n호의 사람수 인데.
예를들어 1층의 1호를 보고자 한다면, 0층의 1호까지 보면 되기 때문에, 1이 되고 2층도 마찬가지라 보면된다.

이후 1층의 2호가 몇 명살고 있는지를 알고 싶다면 0층의 2호까지의 총합을 보면 된다.

문제를 풀기 위해선 약간의 수학적 규칙을 찾으면 되는데.

1	3	6	10	15	21	28	36	45	55
1	2	3	4	5	6	7	8	9	10

1층의 3호는 1층의 2호와 0층의 3호를 더한 값과 같다.

문제에서 2층의 3호도 한 번 구해보자면

1	4	10	20	35	56	84	120	165	220
1	3	6	10	15	21	28	36	45	55
1	2	3	4	5	6	7	8	9	10

2층의 2호와 1층의 3호를 더한 값이 된다

이걸 코드로 풀어보자면

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <cmath>
#define MAX 15
int T,K,N;
int arr[MAX][MAX];

using namespace std;


void Intput()
{
	cin >> T;
}

void InputCase()
{
	cin >> K >> N;
}

void Solution()
{

	//0층은 1~14까지 세팅해준다.
	for (int i = 0; i < MAX; i++)
	{
		arr[0][i] = i + 1;
	}
	//각층의 1호는 1로 초기화한다.
	for (int i = 1; i < MAX; i++)
	{
		arr[i][0] = 1;
	}

	//0층은 세팅 하였으니 1층 부터 다시 세팅해준다.
	for (int i = 1; i < MAX; i++)
	{
		for (int j = 1; j < MAX; j++)
		{
			arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
		}
	}


	while (T != 0)
	{
		T--;
		InputCase();
		cout << arr[K][N - 1] << '\n';
	}
}

void Solved() {
	Intput();
	Solution();
}

int main() {
	Solved();
}

맨 처음 0층을 i + 1 만큼 대입해줌으로써 1 , 2, 3, 4, 5, 6, 7,8 ,9 ,10을 만들고
이후 1층 부터 14층의 1호는 1로 세팅 해주었다.

이후 1층의 2호부터 arr[층 - 1][호] + arr[층][호 - 1]; 로 아까 보았던 그림과 같은 공식을 넣어줌으로써 해결했다.