PS/BOJ

[백준 BOJ][DP] 2775 부녀회장이 될테야

Jubil 2020. 3. 7. 15:38
반응형

링크

https://www.acmicpc.net/problem/2775

 

2775번: 부녀회장이 될테야

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

www.acmicpc.net

풀이

 

DP[i][j]를 i층 j호에 사는 사람들의 수라고 정의합니다.

써보면 DP[i][j] = DP[i-1][j] + DP[i][j-1] 이라는 사실을 알 수 있습니다.

0층 i호에 i명의 사람들이 산다고 했기 때문에 이를 초기 세팅 해주고 DP 배열을 완성한 다음 출력하면 됩니다.

 

 

코드

//2775_부녀회장이 될테야
#include <cstdio>
using namespace std;

int T, k, n, DP[15][15];

int main() {
	scanf("%d", &T);

	for (int i = 1; i <= 14; ++i) DP[0][i] = i;		// 0층 i호

	for (int i = 1; i <= 14; ++i) {				// DP 배열 완성
		for (int j = 1; j <= 14; ++j) {
			DP[i][j] = DP[i - 1][j] + DP[i][j - 1];
		}
	}

	while (T--) {
		scanf("%d\n%d", &k, &n);

		printf("%d\n", DP[k][n]);
	}

	return 0;
}

반응형