baekjoon #2775_부녀회장이 될테야_c++

• 재귀함수 활용

#include <iostream>
using namespace std;

int getCnt(int a, int b) {
    if (a == 0)
        return b;
    if (b == 1)
        return 1;
    
    return (getCnt(a - 1, b) + getCnt(a, b - 1));
}

int main() {
    int T, k, n;
    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> k >> n;
        cout << getCnt(k, n) << '\n';
    }
}

 

• 조건

  -> a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 함

 

ex )

1

2

3

 

T = 1

k = 2

n = 3

-> 테스트 케이스는 하나로, 2층 3호에 몇명이 사는지 구하기

 

이를 통해, 재귀함수 getCnt(int a, int b) 를 정의

 

• 0층의 x호에는 x명이 산다는 조건

  ->  a = 0 이면, 무조건 1 부터 b 까지 1씩 증가 

  ->  b = 1 이면, 무조건 1명만 살고있음

 

  =>  a = 0 일 때, b를 return 하도록 조건 설정

  =>  b = 1 일 때, 1을 return 하도록 조건 설정

 

•   k 층, n호의 사람 수는 a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합과 같음

  a - 1 층 b호의 사람 수 + a 층 b - 1호의 사람 수

 

  getCnt(a - 1 , b) + getCnt(a , b - 1) 

  위 식을 이용해 자기 자신에게 return

  

  k 와 n 을 대입하면

  getCnt(k ,  n)

 

  -> getCnt(k - 1 , n) + getCnt(k , n - 1)

재귀함수 동작 과정

 

 

잘 모르겠어서 아래 블로그를 참고하였음

https://aorica.tistory.com/125