[백준알고리즘] 2775번: 부녀회장이 될테야 -C++

[백준알고리즘] 2775번: 부녀회장이 될테야 -C++

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

2775번: 부녀회장이 될테야

동적 계획법을 이용해 풀었다.

 

\(i\) 층 \(j\)호에는 \(i-1\) 층의 \(0\) 호부터 \(j\)호의 모든 거주민의 수만큼 살고 있다.

이때 \(0\)호부터 \(j-1\) 호까지의 모든 거주민의 수는 \(i\) 층의 \(j-1\) 호에 살고 있는 사람 수와 같다.

 

 

따라서 dp[i][j] = dp[i-1][j] + dp[i][j-1]이 성립하게 된다.

 

#include <iostream>

void solve(void);

int main(void)
{
	int test_case;
	std::cin >> test_case;

	for (int t = 0; t < test_case; t++)
		solve();
}

void solve(void)
{
	int k, n;
	std::cin >> k >> n;
	
	int dp[15][15] = { 0 };

	for (int i = 0; i < 15; i++)
		dp[0][i] = i;

	for (int i = 1; i <= k; i++)
		for (int j = 1; j <= n; j++)
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

	std::cout << dp[k][n] << std::endl;
}

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다