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

풀이

 

예를 들어, 2층 3호의 거주민 수를 알고 싶다면 0층의 1호 ~ 3호의 거주민 수, 1층의 1호 ~ 3호 거주민 수를 알고 있으면 된다. 즉, k층의 n호의 거주민 수를 알고 싶다면 (k-1)층 까지의 1호 ~ n호 거주민 수를 알고 있으면 된다. 

 

먼저, 동적할당으로 n 사이즈의 배열을 선언 후, 0층의 1호(배열 index : 0)에서 n호 (배열 index : 1) 의 거주민 수를 초기화 한다. 

이후 1층부터 K층까지 차례대로 거주민 수를 계산하게 된다

 

다이나믹 프로그래밍이라는 힌트를 알게되면 무난하게 풀 수 있는 문제이다.

 

#include <iostream>
int main() {
	int t; //test case num
	std::cin >> t;

	int k, n; // k : floor, n : room num

	for (int i = 0; i < t; i++) {
		std::cin >> k >> n;

		int* arr = new int[n];

		for (int j = 0; j < n; j++) {
			arr[j] = j + 1;
		}

		for (int x = 1; x <= k; x++) { 
			for (int y = 1; y < n; y++) {
				arr[y] += arr[y - 1];
			}
		}

		std::cout << arr[n-1] << std::endl;
		delete[] arr;
	}
}