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

문제

 

---

풀이

 

동적 계획법으로도 풀 수 있을 것 같은데 나는 재귀함수로 풀었다. 입력이 둘 다 1이상으로 들어온다고 하니, 굳이 0층의 사람까지 따질 필요는 없을 것 같다. 0층의 i호에는 i명이 산다고 하니, 1층의 i호에는 1+2+...+i명이 살 것이다. 그보다 높은 층에 대해서도 이 논리는 변하지 않으니 이대로 재귀함수를 짜면 된다.

---

소스코드

 

#include <iostream>
using namespace std;

int live(int k, int n) { //재귀함수
	int people = 0;
	if (k == 1) {
		for (int i = 1; i <= n; i++)
			people += i;
	}
	else {
		for (int i = n; i >= 1; i--)
			people += live(k - 1, i);
	}
	return people;
}

int main() {
	int T, k, n;

	cin >> T;
	for (int i = 0; i < T; i++) {
		cin >> k >> n;
		cout << live(k, n) << endl;
	}
}