Baekjoon 문제 2775번 부녀회장이 될테야

문제 출처:https://www.acmicpc.net/problem/2775

2775번: 부녀회장이 될테야

Baekjoon 2775번 문제 부녀회장이 될테야

---

해당 문제는 파스칼의 삼각형과 같은 형태로 호실을 구성합니다.

[EBSMath 파스칼의 삼각형에서 발견할 수 있는 정리]

이것을 알고 있다면 S(a, b) = s(a-1, b) + s(a, b-1)으로 값을 표현할 수 있습니다.

저는 재귀적으로 문제를 접근했습니다. 호수는 0이 올 수 없기 때문에 b==1일 때, a는 0층이 제일 낮은 층이므로 0일 때가 base case입니다.

---

코드는 다음과 같습니다:

#include <iostream>

using namespace std ;

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

int main(){
    ios::sync_with_stdio(false) ;
    cin.tie(NULL) ; cout.tie(NULL) ;

    int T, k ;  short n ;
    cin >> T ;
    for(int i = 0 ; i < T ; i++){
        cin >> k >> n ;
        cout << getNum(k, n) << endl ;
    }
    return 0 ;
}

해당 문제는 Github에서도 보실 수 있습니다:

https://github.com/gurcks8989/CodingTest/blob/master/BackJoon/HPS/P2775_I_will_be_the_President_of_Women_Society.cpp

GitHub - gurcks8989/CodingTest: CodingTest_study_with_c++

훈수 및 조언은 언제든 환영입니다.