2775 부녀회장이 될테야 (조합론) [Bronze I]

2775번: 부녀회장이 될테야 (acmicpc.net)

이항계수 구하기

이항계수 구하기와 굉장히 비슷한 문제

 

문제 핵심

“a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다”

"0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다."

 

0층 i호에는 i명이 살고 있고, 모든 호의 1호에는 1명이 살고있다는것을 도출할 수 있음

{1, 0, 0, 0} // 3층
{1, 0, 0, 0} // 2층
{1, 0, 0, 0} // 1층
{1, 2, 3, 4} // 0층
1호  ~   4호

 

1층의 2호에 사는 사람 수는 0층 1 ~ 2호 즉 1층 1호 + 0층 2호라는 것을 알 수 있음이것을 토대로 점화식을 만들 수 있는데

array[1층][2호] = array[1층][1호] + array[0층][2호];

반복문을 이용해서 모든 층을 업데이트 해주면 해결 됨

 

array[1층][2호] = array[1층][1호] + array[0층][2호];
array[1층][3호] = array[1층][2호] + array[0층][3호];
array[1층][4호] = array[1층][3호] + array[0층][4호];

array[2층][2호] = array[2층][1호] + array[1층][2호];
array[2층][3호] = array[2층][2호] + array[1층][3호];
array[2층][4호] = array[2층][3호] + array[1층][4호];

array[3층][2호] = array[3층][1호] + array[2층][2호];
array[3층][3호] = array[3층][2호] + array[2층][3호];
array[3층][4호] = array[3층][3호] + array[2층][4호];

 

정답 코드

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

static int D[1001][1001]; 

void result()
{
	int k, n;
	cin >> k >> n;

	for (int i = 1; i <= n; i++) {
		D[0][i] = i; 
	}
	for (int i = 1; i <= k; i++) {
		D[i][1] = 1;
	}
	
	for (int i = 1; i <= k; i++) 
	{
		for (int j = 2; j <= n; j++) 
		{
			D[i][j] = D[i][j - 1] + D[i - 1][j];
		}
	}

	cout << D[k][n] << "\n";
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;

	for (int i = 0; i < N; i++) {
		result();
	}


}