_2775

문제출처: https://www.acmicpc.net/problem/2775

2775번: 부녀회장이 될테야

계차수열에 관한 문제다. 실제로 표로 그려 규칙을 찾아보면 같은층의 왼쪽(K, N-1)과 바로 아래층(K-1, N)의 수를 합친 것과 같음을 알 수 있다. 따라서 int형 2차원 배열 arr에 각 층의 인원 수를 적은 후 arr[K][N]을 리턴해주면 된다.

 

#include <iostream>

using namespace std;

int arr[15][15];

int residentNumber(int K, int N) { // K층, N호

	for (int i = 1; i <= N; i++) {
		arr[0][i] = i;
	} // 0층의 주민 수 1, 2, 3 ...은 계차수열 법칙을 따르지 않으므로 따로 정의해준다.

	for (int i = 1; i <= K; i++) {
		for (int j = 1; j <= N; j++) {
			arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
		}
	} // 같은 층의 왼쪽 (arr[i-1][j]) + 바로 아래층 (arr[i][j-1])의 합이
      // arr[i][j], 즉 K'층 N'호의 인원 수.

	return arr[K][N];
}

int main() {
	int T, K, N;

	cin >> T; // Test case 수를 입력 받는다.
	
	for (int i = 0; i < T; i++) {
		cin >> K;
		cin >> N;
		cout << residentNumber(K, N) <<endl;
	}
}