[백준] 2775번: 부녀회장이 될테야

문제링크 : https://www.acmicpc.net/problem/2775

 

문제풀이

처음에는 이 문제의 규칙을 찾으려고 했다.

하지만 문제를 다시 보니 입력받는 수가 크지 않아서 (1 <= k <= 14, 1 <= n <= 14)

14층 14호까지 모든 거주민 수를 구하는 데 시간이 많이 걸리지 않을 것 같다는 생각이 들었다.

그래서 14호 14층까지 채울 수 있는 2차원 배열을 만들어, 모든 경우를 다 계산해 놓았다.

0층에 해당하는 값들만 세팅해 놓고, 1층 1호부터 순서대로 아래층을 더해서 계산한다.

빨간색의 2층 3호인 경우에는, 1층의 1호, 2호, 3호의 수를 더하면 된다.

 

소스코드

/*
 * 백준 2775번: 부녀회장이 될테야
 */

#include <iostream>

using namespace std;

int main() {
	int T;
	cin >> T;

	int arr[15][15];
	// 0층 값 세팅
	for (int i = 1; i < 15; i++) {
		arr[0][i] = i;
	}

	for (int i = 1; i < 15; i++) {
		for (int j = 1; j < 15; j++) {
			int sum = 0;
			for (int k = 1; k <= j; k++) {
				sum += arr[i - 1][k];
			}
			arr[i][j] = sum;
		}
	}

	while (T--) {
		int k, n;
		cin >> k >> n;
		cout << arr[k][n] << endl;
	}
	
	return 0;
}