부녀회장이 될테야 (feat. 백준, 2775번)

부녀회장이 될테야
https://www.acmicpc.net/problem/2775

2775번: 부녀회장이 될테야

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/2775
#include <iostream>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int T, K, N, dp[15][15] = { 0 };
	for (register int i = 1; i <= 14; ++i)
		dp[0][i] = i;
	for(register int i = 1, j; i <= 14; ++i)
		for(j = 1; j <= 14; ++j)
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
	cin >> T;
	for (register int t = 0; t < T; ++t) {
		cin >> K >> N;
		cout << dp[K][N] << endl;
	}
	return 0;
}
// *&)*@*

아래의 그림처럼 가구당 세대원수는 규칙적으로 정해져있습니다.

여기서 3층의 4호는 몇명이 살아야 할까요?

3층의 4호는 3층의 3호 세대원과 2층의 4호 세대원을 합친 세대원이 되어야 하므로 35 입니다.

즉, P[K][N] = P[K - 1][N] + P[K][N - 1] 이라는 식이 도출되는 것을 알 수 있습니다.