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

문제 링크

코드

#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(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t, k, n;
    cin >> t;
    while (t--) {
        cin >> k >> n;
        cout << func(k, n) << '\n';
    }
}

---

설명

수열의 규칙을 파악해보자.
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 한다.

n의 범위가 14까지로 제한되어 있어서 재귀 함수를 이용해도 시간 초과가 안 날 것이라고 생각했다.

(주의) 기록용으로 작성한 글입니다. 좋은 코드가 아닐 수 있습니다.

댓글 환영합니다!