백준 블로그 글을 보며 공부한 내용입니다.
원래 코드 및 글 : https://www.acmicpc.net/blog/view/28
#include <iostream>
#include <vector>
using namespace std;
typedef vector<vector<long long>> matrix;
const long long mod = 1000000007LL;
//연산자 재 정의.
// 정사각행렬의 곱셈
//c++는 객체에 따라서 연산자를 알아서 바꿔서 해석해주므로 그냥 * 로 이용할 수 있음
matrix operator * (const matrix &a, const matrix &b){
int n = a.size();
//vector <long long> v(n,0) means you're creating a vector of size n and initializing its elements to 0
//행렬 c은 vector<long long>(n) 를 원소로 갖는 벡터 n개
matrix c(n, vector<long long>(n));
for(int i = 0 ; i < n ; i ++){
for(int j = 0 ; j < n ; j++){
for(int k = 0 ; k < n ; k ++){
c[i][j] += a[i][k]*b[k][j];
}
// 이 부분은 그냥 피보나치 문제에서 주어진것 1000000007LL 로 모듈로 한 값을 반환하라 했음
c[i][j] %= mod;
}
}
return c;
}
int main() {
long long n;
cin >> n;
if (n <= 1) {
cout << n << '\n';
return 0;
}
matrix ans = {{1, 0}, {0, 1}};
matrix a = {{1, 1}, {1, 0}};
/*
* n==11일 때
* 11%2 = 1 -> ans = ans*a 하면 그냥 a;
* 11/2 = 5 하고 a = {{1, 1}, {1, 0}}^2;
*
* 5%2 = 1 -> ans = a*a^2 = {{1, 1}, {1, 0}}^3
* 5/2 = 2 하고 a 값은 {{1, 1}, {1, 0}}^4
*
* 2%2 = 0
* 2/2 = 1 하고 a값은 {{1, 1}, {1, 0}}^8
*
* 1%2 = 1 -> ans = {{1, 1}, {1, 0}}^3 * {{1, 1}, {1, 0}}^8 = {{1, 1}, {1, 0}}^11;
* -끝
*
* 이걸 어떻게 알았담..
* */
while (n > 0) {
if (n % 2 == 1) {
ans = ans * a;
}
a = a * a;
n /= 2;
}
cout << ans[0][1] << '\n';
return 0;
} |
[새로 알게된 내용]
* typedef vector<vector<long long>> matrix;
간단하게 한줄짜리 typedef
* matrix c(n, vector<long long>(n));
c라는 메트릭스를 새로 선언하고, 안에 길이 n짜리 벡터를 넣는데 이 각각 벡터들은 또 길이 n짜리 long long 벡터 초기화 되어있음
다른예시
vector <long long> v(n,0)
벡터 v는 길이 n짜리 long long 벡터이며 각각 원소들은 0으로 초기화 되어있음.
*const long long mod = 1000000007LL;
long long int 선언
*matrix operator * (const matrix &a, const matrix &b){
연산자 재정의....! *연산자를 객체에 따라 다르게 작동하도록 오버로딩 할 수 있음
(갑자기 헷깔려서 찾아봄 : 오버로딩은 같은 함수 이름을 피연산자에 따라 다르게 사용하는것, 오버라이딩은 부모 클라스의 메서드에 덮어쓰는것)
*행렬연산 알고리즘
for(int i = 0 ; i < n ; i ++){
for(int j = 0 ; j < n ; j++){
for(int k = 0 ; k < n ; k ++){
c[i][j] += a[i][k]*b[k][j];
}
}
}
|
혼자 짤려고 했으면 어떻게 접근할지 고민 했을듯...
*행렬 거듭제곱 빠르게 알고리즘
matrix ans = {{1, 0}, {0, 1}}; while (n > 0) {
if (n % 2 == 1) {
ans = ans * a;
}
a = a * a;
n /= 2;
}
|