백준 알고리즘 2775

#include 
#include
using namespace std;
int memoization[15][15];
void init() {
	for (int i = 0; i < 15; i++) {
		memoization[0][i] = i;
	}
	for (int i = 1; i < 15; i++) {
		memset(&memoization[i][0], 0, 15 * 4);
	}
}
int dp_room(int k, int n) {
	if (memoization[k][n] != 0) {
		return memoization[k][n];
	}
	else {
		int temp = 0;
		for (int i = 1; i <= n; i++) {
			temp = temp + dp_room(k - 1, i);
		}
		memoization[k][n] = temp;
		return temp;
	}
}

int main() {
		init();
		int T;
		cin >> T;
		int k, n;
		for (int i = 0; i < T; i++) {
			cin >> k >> n;
			cout << dp_room(k, n);
			if (i != T - 1)
				cout << "\n";
		}

	return 0;
}

해당문제의 조건은 1<= k,n <= 14이기 때문에 dp를 사용하지 않아도 풀 수 있는 문제지만.

보고나서 바로 dp를 사용해야겠다는 생각을 했기 때문에 dp를 구현.

아랫층의 1~n까지의 숫자를 더해야한다는 확실한 규칙이 있기때문에 dp를 적용할 수 있다.