[백준/BOJ] 2775번 - 부녀회장이 될테야 (C++)

문제 링크

 

코딩하기 전 생각하기

/*
수열의 규칙을 파악해본다.
1  2  3  4  5
1  3  6  10 15
1  4  10 20 35
1  5  15 35 70
1  6  21 56 126
(k, n)의 숫자는 (k, n-1)의 숫자와 (k-1, n)의 숫자를 더한 수이다.
재귀 함수를 선언하자.
0번째 층일 때는 n을 return 하고,
1호일 때는 1을 return 한다.
*/

 

---

 

코드

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

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

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

 

---

 

느낀점

 

아무리 생각해도 수열의 일반항이 구해지지 않아서 재귀 함수를 이용하기로 했다. 시간 초과가 날까 봐 겁먹긴 했지만 n의 범위가 14까지로 제한되어 있어서 진행해도 될 것 같았다.

좋은 날 싫은 날 문제와는 다르게 이번 수학문제는 재귀로 통과할 수 있어서 좋았다.

 

(주의) 기록용으로 작성한 글입니다. 코드가 허접하거나 알고리즘의 효율이 낮을 수 있습니다.

댓글 환영합니다!