💡 조합론/다이나믹 프로그래밍/수학
Memory 56584KB Time 44ms Code Length 308B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
using namespace std;
long long d[1'000'001];
int N;
void init() {
cin >> N;
d[1] = 0;
d[2] = 1;
}
long long solve(int N) {
if (N <= 1) return 0;
if (d[N] == 0) d[N] = (N - 1) * (solve(N - 1) + solve(N - 2)) % 1'000'000'000;
return d[N];
}
int main() {
init();
cout << solve(N);
}
~ 이 코드는 피보나치 수열을 구하는 함수를 구현한 것이다. init() 함수에서는 N을 입력받고, d 배열의 초기값을 설정한다. solve() 함수에서는 재귀적으로 N번째 피보나치 수를 계산하는데, 이미 계산한 값은 배열 d에 저장하여 중복 계산을 피한다. main() 함수에서는 init()을 호출하여 N을 입력받고, solve()를 호출하여 N번째 피보나치 수를 출력한다.
