백준 2775번 [부녀회장이 될테야](C++)-yes6686- 티스토리

백준 문제 풀이: 2775 [부녀회장이 될테야]

---

문제 링크: https://www.acmicpc.net/problem/2775

문제 설명:

아파트의 k층 n호에 살기 위해서는 아래층 사람 수의 합을 모두 더해야 합니다. 0층의 n호에는 n명의 사람이 삽니다. k층 n호의 사람 수를 출력하는 문제입니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int sum = 0;

// k층 n호의 주민 수 계산
int residents(int k, int n) {
    if (k == 0) {
        sum += n;
    } else {
        for (int i = 1; i <= n; i++) {
            residents(k - 1, i);
        }
    }
    return sum;
}

int main() {
    int T; // 테스트 케이스 개수
    cin >> T;
    int k, n;
    while (T--) {
        cin >> k >> n;
        cout << residents(k, n) << '\n';
        sum = 0; // sum 초기화
    }
}

---

코드 설명

• 핵심 알고리즘: 재귀를 통해 아파트 층과 호수의 주민 수를 계산
• 구현 세부사항:
  • 0층 n호에는 n명의 주민이 있음
  • k층 n호의 주민 수는 (k-1)층 1호부터 n호까지의 주민 수의 합으로 계산
  • 매 테스트 케이스마다 sum을 초기화하여 결과를 정확히 계산
• 시간 복잡도: O(k⋅n⋅n)
  • 중첩된 재귀 호출로 인해 효율적이지 않음

---

결과

각 테스트 케이스에 대해 k층 n호의 주민 수를 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!