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

문제

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

2775번: 부녀회장이 될테야

소스코드

#include <iostream>
#include <algorithm>
#include <string>
#include <math.h>
#include <vector>
using namespace std;
int arr[15][15];
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL); 
	int T;
	cin >> T;
	for (int i = 0; i < 15; i++) {
		for (int j = 0; j < 15; j++) {
			if (i == 0 || j == 0) {
				arr[i][j] = j+1;
			}
			else {
				arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
			}
		}
	}
	
	while (T--) {
		int k, n;
		cin >> k >> n;
		cout << arr[k][n-1]<<"\n";
	}
}

해설

a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다

이 조건을 자세히 살펴본다.

1층의 3호에 살기위해서는 0층의 1호+2호+3호의 사람들의 수를 합쳐줘야한다.

결국 이렇게 그리면서 패턴을 파악해보면

이렇게 된다는 것을 알 수 있으니, 점화식을 작성해서 배열에 넣어주면된다.