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

백준 2775번 - 부녀회장이 될테야

백준 2775번

❓ 문제

평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다.

이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다.

아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.

---

✏️ 풀이

이 문제는 input으로 n,k를 받았을 때, n층 k호에 사는 사람의 수를 출력하는 문제이다.

조건 :

1. 아파트는 0층부터
2. 각층에는 1호부터
3. 0층 i호에는 i명이 산다

그렇다면 0층부터 표로 그려보자.

	1호	2호	3호	4호	5호
2층	1	4	10	20	35
1층	1	3	6	10	15
0층	1	2	3	4	5

이정도를 그려봤을 때, 이 아파트의 거주민 수 조건을 알 수 있었다.

1. 모든 1호에는 1명만 산다.
2. 0층의 k호는 k명이 산다.
3. 그 외의 (n층, k호)에는 (같은 층 k-1호) + (아래 층 같은 k호) = 거주민 수

따라서, recursion으로 이 식을 표현해보자.

int recursion(int k, int n) {
  if (k==0)
    return n;
  if (n==1)
    return 1;
  return recursion(k-1, n) + recursion(k, n-1);
}

위의 조건으로 (n층, k호) 주민 수를 알 수 있게된다.
뭔가 같은 값을 계속 조회하는 것은 비효율적이라 dp memoization을 사용해야할 것 같지만, 정답을 맞췄으므로 일단은 넘어가도록 하자.

---

✔️ 정답 코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> answer;

int recursion(int k, int n);

int main(void) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int N;
  cin >> N;

  for (int i=0; i<N; i++) {
    int k,n;
    cin >> k >> n;
    answer.push_back(recursion(k,n));
  }

  for (int i=0; i<answer.size(); i++)
    cout << answer[i] << "\n";
  
  return 0;
}

int recursion(int k, int n) {
  if (k==0)
    return n;
  if (n==1)
    return 1;
  return recursion(k-1, n) + recursion(k, n-1);
}