BOJ 11444. 피보나치 수 6
랭크 : 골드2
문제 풀이
F2n + 1, Fn을 구한다면 F2n은 Fn계수로 F0의 계수를 Fn에 F1의 계수를 F2n + 1에 조합한 것과 같으므로, 분할정복이 가능합니다. 머리는 이해를 했는데 실제 구현하는 게 시간이 좀 걸렸습니다.
#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using ull = unsigned long long;
using namespace std;
struct Fibo {
ull a, b;
Fibo(ull x, ull y) : a(x), b(y) {};
Fibo(){};
};
map<ull, Fibo> mapping;
void dfs(ull step) {
if (mapping.find(step) != mapping.end()) return ;
dfs(step/2); dfs(step/2 + 1);
Fibo tmp = {((mapping[step/2 + 1].a * mapping[step/2].a) % 1'000'000'007 + (mapping[step/2].a * mapping[step/2].b) % 1'000'000'007) % 1'000'000'007,
((mapping[step/2].b * mapping[step/2].b) % 1'000'000'007 + (mapping[step/2 + 1].b * mapping[step/2].a) % 1'000'000'007) % 1'000'000'007};
if (step % 2) {
ull tmp1 = (tmp.a + tmp.b) % 1'000'000'007;
tmp.b = tmp.a;
tmp.a = tmp1;
}
// cout << step << " " << tmp.a << " " << tmp.b << endl;
mapping[step] = tmp;
}
int main() {
fastio;
ull N;
cin >> N;
mapping[1] = {1, 0};
mapping[2] = {1, 1};
mapping[3] = {2, 1};
dfs(N);
cout << mapping[N].a << endl;
}
알고리즘 |
시간복잡도 |
공간복잡도 |
|---|---|---|
| merge & conquer | $O(log N)$ | $O(log N)$ |
'알고리즘 > 백준' 카테고리의 다른 글
| BOJ 11657. 타임머신 (0) | 2022.07.17 |
|---|---|
| BOJ 1655. 가운데를 말해요 (0) | 2022.07.17 |
| BOJ 17298. 오큰수 (0) | 2022.07.17 |
| BOJ 1450. 냅색문제 (0) | 2022.07.17 |
| BOJ 11054. 가장 긴 바이토닉 부분 수열 (0) | 2022.07.17 |