반응형
https://www.acmicpc.net/problem/11444
11444번: 피보나치 수 6
첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.
www.acmicpc.net
[ 문제풀이 ]
분할 정복과 도가뉴의 방정식을 이용하면 쉽게 풀 수 있는 문제입니다. 또한 시간 초과를 방지하기 위해서 메모제이션을 해주어야 하는데 n의 값이 매우 크므로 unordered_map을 활용하여 문제를 풀었습니다.
도가뉴의 방정식은 다음과 같습니다.
$a_{2n}=a_{n}(a_{n} + 2a_{n-1})$
$a_{2n-1}=a_{n}^{2}+a_{n-1}^{2}$
[ 소스 코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | #include<iostream> #include<unordered_map> #define ll long long using namespace std; ll n; unordered_map<ll, ll> m; ll conquer(ll num) { if (num == 1) return 1; if (num == 0) return 0; if (m[num] != 0) return m[num]; if (num % 2 == 0) { //도가뉴의 항등식 ll temp = num / 2; m[num] = conquer(temp)*(conquer(temp) + 2 * conquer(temp - 1)); return m[num] %= 1000000007; } else { ll temp = (num + 1) / 2; m[num] = conquer(temp) * conquer(temp) + conquer(temp - 1) * conquer(temp - 1); return m[num] %= 1000000007; } } int main() { scanf("%lld", &n); printf("%lld", conquer(n)); } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 1629번 - 곱셈 (C++) (0) | 2022.08.01 |
|---|---|
| [ 백준 ] 11725번 - 트리의 부모 찾기 (C++) (0) | 2022.07.31 |
| [ 백준 ] 2243번 - 사탕상자 (C++) (0) | 2022.07.29 |
| [ 백준 ] 5719번 - 거의 최단 경로 (C++) (0) | 2022.07.27 |
| [ 백준 ] 2618번 - 경찰차 (C++) (0) | 2022.07.26 |