문제 설명
“부녀회장이 될 테야” 문제는 아파트의 층과 호수에 따라 사람의 수를 계산하는 문제입니다.
주어진 층의 인덱스와 호수의 인덱스를 통해 몇 명이 거주하는지를 파악해야 합니다.
이 문제의 핵심은 피라미드 구조를 활용하여 각 층에서의 거주자 수를 계산하는 것입니다.
문제 이해하기
어느 아파트에 거주하는 사람의 수를 정의하는 규칙은 다음과 같습니다.
0층(i=0)의 경우, i호는 항상 1명입니다.
1층(i=1)에서는 i호가 1명에서 시작해, 위층의 모든 호수에 해당하는 사람의 수를 합산하여 나타납니다.
즉, f(n, k)는 n층 k호의 사람 수를 나타내면, 다음과 같은 재귀 방정식을 세울 수 있습니다:
f(n, k) = f(n-1, 1) + f(n-1, 2) + ... + f(n-1, k)이 규칙을 바탕으로, n층 k호에 거주하는 사람 수는 (n-1)층 1호부터 k호까지의 합입니다.
문제 풀이 접근법
1. **기본 재귀 함수 구현**: 문제를 단순하게 풀기 위해, 재귀적으로 많은 호출이 발생하는 방법을 사용할 수 있습니다.
2. **동적 프로그래밍 활용**: 재귀적인 접근 방식은 동일한 값을 여러 번 호출할 수 있어 비효율적입니다.
세부적인 결과를 저장하는 메모이제이션(또는 다이나믹 프로그래밍)을 통해 성능을 개선할 수 있습니다.
이 문제는 층과 호수를 기반으로 테이블을 생성하여, 모든 계산된 값들을 저장할 수 있습니다.
C++ 코드 구현
아래의 코드는 동적 프로그래밍을 사용하여, 주어진 층과 호수의 사람 수를 계산하는 방식입니다:
#include <iostream>
#include <vector>
using namespace std;
int main() {
int T; // 테스트 케이스 수
cin >> T;
while (T--) {
int k, n; // k: 호수, n: 층
cin >> k >> n;
vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
// 0층 초기화
for (int i = 1; i <= k; ++i) {
dp[0][i] = 1; // 0층 i호에는 항상 1명
}
// DP 테이블 구성
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= k; ++j) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
// 결과 출력
cout << dp[n][k] << endl;
}
return 0;
}
시간 복잡도 분석
위의 구현 방식은 T개의 테스트 케이스에 대해 각각 n층 k호까지 계산하므로, 최악의 경우 O(n * k)의 시간 복잡도를 가집니다.
구현된 동적 프로그래밍 방식은 공간 복잡도 또한 O(n * k)를 요구합니다.
결론
“부녀회장이 될 테야” 문제는 문제의 규칙을 이해하고, 적절한 알고리즘을 선택해 구현함으로써 효율적으로 해결할 수 있습니다.
C++의 동적 프로그래밍 기법을 통해 성능을 극대화할 수 있으며, 이러한 접근은 다양한 유사한 문제를 풀 때에도 유용하게 사용할 수 있습니다.
추가 문제 및 연습
문제를 더 깊이 이해하고 싶다면, 다음과 같은 변형 문제를 시도해보는 것을 추천합니다:
- 층의 수를 고정하고 호수를 변화시키기
- 층과 호수를 반대로 바꿔서 문제를 설정하기
- 기존의 DP 테이블을 최적화하여 공간 복잡도 줄이기