백준 11444, 피보나치 수 6
문제
https://www.acmicpc.net/problem/11444
풀이
이 문제는 못풀어서 풀이 방법을 봤다... 따라서 상세 풀이 설명을 생략하겠다.
처음에는 n 탐색으로는 절대 안될 것 같아서 로그 탐색으로 할 수 있나 생각해 봤지만 쉽게는 안풀릴 것 같아 혹시 수학 관련 문제인가 싶어
이런 식을 푸는 과정을 통해 같을 꼴로 나타내어 제곱 분할 정복을 만들려 했지만 실패했다.
그래도 1시간 정도 생각하다가 포기 하고 정답을 봤는데... 행렬 곱셈을 통한 풀이 였다.
선형대수를 제대로 공부하지 않아서 발생한 문제라 생각된다... 복습해야겠다.
실수
- 구현 과정에서 ret = ret와 같이 값을 바로 사용하려다가 로직을 제대로 파악하지 못하여 값이 꼬이는 상황이 발생, 결국 temp를 만들어 해결 (시간 낭비)
- 행렬 곱셈을 한지 오래되어 구현하는데 시간이 오래걸림
코드
#define _CRT_SECURE_NO_WARNINGS
#include<vector>
#include<iostream>
using namespace std;
vector<vector<long long int>> ret_mat = { {1, 1}, {1, 0} }; // 재귀에서 반환할 행렬
vector<long long int> init = { 1, 1 };
vector<vector<long long int>> u = { {1, 1}, {1, 0} };
void DC(long long int n) {
if (n == 1) {
ret_mat[0][0] = u[0][0];
ret_mat[1][0] = u[1][0];
ret_mat[0][1] = u[0][1];
ret_mat[1][1] = u[1][1];
return;
}
else {
if (n % 2 == 1) {
DC((n - 1) / 2);
vector<vector<long long int>> temp = { {0, 0}, {0, 0} };
temp[0][0] = ret_mat[0][0];
temp[1][0] = ret_mat[1][0];
temp[0][1] = ret_mat[0][1];
temp[1][1] = ret_mat[1][1];
ret_mat[0][0] = temp[0][0] * temp[0][0] + temp[0][1] * temp[1][0];
ret_mat[0][1] = temp[0][0] * temp[0][1] + temp[0][1] * temp[1][1];
ret_mat[1][0] = temp[1][0] * temp[0][0] + temp[1][1] * temp[1][0];
ret_mat[1][1] = temp[1][0] * temp[0][1] + temp[1][1] * temp[1][1];
temp[0][0] = ret_mat[0][0];
temp[1][0] = ret_mat[1][0];
temp[0][1] = ret_mat[0][1];
temp[1][1] = ret_mat[1][1];
ret_mat[0][0] = temp[0][0] * u[0][0] + temp[0][1] * u[1][0];
ret_mat[0][1] = temp[0][0] * u[0][1] + temp[0][1] * u[1][1];
ret_mat[1][0] = temp[1][0] * u[0][0] + temp[1][1] * u[1][0];
ret_mat[1][1] = temp[1][0] * u[0][1] + temp[1][1] * u[1][1];
ret_mat[0][0] = ret_mat[0][0] % 1000000007;
ret_mat[0][1] = ret_mat[0][1] % 1000000007;
ret_mat[1][0] = ret_mat[1][0] % 1000000007;
ret_mat[1][1] = ret_mat[1][1] % 1000000007;
}
else {
DC(n / 2);
vector<vector<long long int>> temp = { {0, 0}, {0, 0} };
temp[0][0] = ret_mat[0][0];
temp[1][0] = ret_mat[1][0];
temp[0][1] = ret_mat[0][1];
temp[1][1] = ret_mat[1][1];
ret_mat[0][0] = temp[0][0] * temp[0][0] + temp[0][1] * temp[1][0];
ret_mat[0][1] = temp[0][0] * temp[0][1] + temp[0][1] * temp[1][1];
ret_mat[1][0] = temp[1][0] * temp[0][0] + temp[1][1] * temp[1][0];
ret_mat[1][1] = temp[1][0] * temp[0][1] + temp[1][1] * temp[1][1];
ret_mat[0][0] = ret_mat[0][0] % 1000000007;
ret_mat[0][1] = ret_mat[0][1] % 1000000007;
ret_mat[1][0] = ret_mat[1][0] % 1000000007;
ret_mat[1][1] = ret_mat[1][1] % 1000000007;
}
return;
}
}
int main() {
long long int n;
scanf("%lld", &n);
DC(n);
printf("%lld", ret_mat[1][0]);
return 0;
}
Author And Source
이 문제에 관하여(백준 11444, 피보나치 수 6), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sukha5364/백준-11444-피보나치-수-6저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)