글 읽기 - 2086 시간초과

kcl5363 6년 전 0

행렬로 피보나치를 풀었는데 시간초과가 떠서 어떤 부분이 잘못됬는지 모르겠습니다.

가르쳐 주세요 ㅠㅠㅠㅠㅠㅠㅠㅠ

#include <iostream>

using namespace std;

double Metrix[2][2]={{1,1},{1,0}};
double internal_value[2][2]={{1,1},{1,0}};
int temp[2][2]={0};
double store[2][2]={0};

int pow_Metrix(int num){
	if(num==1)return 1;
	else if(num==2)return 1;
	else{
		while(num!=2){
			for(int i=0;i<2;i++){
				for(int j=0;j<2;j++){
					store[i][j]=Metrix[i][j];
				}
			}
		Metrix[0][0]=store[0][0]*internal_value[0][0]+store[0][1]*internal_value[1][0];
			temp[0][0]=(int)Metrix[0][0]%1000000000;
			Metrix[0][0]=temp[0][0];
			Metrix[0][1]=store[0][0]*internal_value[0][1]+store[0][1]*internal_value[1][1];
			temp[0][1]=(int)Metrix[0][1]%1000000000;
			Metrix[0][1]=temp[0][1];
		
			num--;
		}
		Metrix[0][0]=1;
		Metrix[0][1]=1;
		Metrix[1][0]=1;
		Metrix[1][1]=0;
		return temp[0][0]%1000000000;
	}
	
}
int main(){
	int num1,num2;
	cin>>num1>>num2;
	cout<<pow_Metrix(num2+2)-pow_Metrix(num1+1)<<endl;
	
	return 0;
}

jh05013 6년 전 0

a와 b는 int 범위가 아닙니다.

kcl5363 6년 전 0

문제 다시읽고 코드 수정했는데 시간초과문제는 어떻게 해결할 수 있을까요? 불필요한 부분이 있나요? 행렬로 푸는 것보다 더 빨리 풀 수 있는 방법이 있을까요?? 도와주세요ㅠ

#include <iostream>

using namespace std;

long long Metrix[2][2]={{1,1},{1,0}};
long long internal_value[2][2]={{1,1},{1,0}};
long long temp[2][2]={0};
long long store[2][2]={0};

unsigned long long pow_Metrix(unsigned long long num){
	if(num==1)return 1;
	else if(num==2)return 1;
	else{
		while(num!=2){
			for(int i=0;i<2;i++){
				for(int j=0;j<2;j++){
					store[i][j]=Metrix[i][j];
				}
			}
		Metrix[0][0]=store[0][0]*internal_value[0][0]+store[0][1]*internal_value[1][0];
			temp[0][0]=(unsigned long long)Metrix[0][0]%1000000000;
			Metrix[0][0]=temp[0][0];
			Metrix[0][1]=store[0][0]*internal_value[0][1]+store[0][1]*internal_value[1][1];
			temp[0][1]=(unsigned long long)Metrix[0][1]%1000000000;
			Metrix[0][1]=temp[0][1];
		
			num--;
		}
		Metrix[0][0]=1;
		Metrix[0][1]=1;
		Metrix[1][0]=1;
		Metrix[1][1]=0;
		return temp[0][0]%1000000000;
	}
	
}
int main(){
	unsigned long long num1,num2;
	cin>>num1>>num2;
	cout<<pow_Metrix(num2+2)-pow_Metrix(num1+1)<<endl;
	
	return 0;
}

jh05013 6년 전 0

행렬 제곱을 하는 데 O(n)이 걸리면 여기서 쓰는 의미가 없습니다. 행렬 거듭제곱에 대해 알아보세요.

Green55 6년 전 0

1629 곱셈 문제를 한번 풀어보세요.

https://www.acmicpc.net/proble...

kcl5363 6년 전 0

1629 곱셈문제 거듭제곱 알고리즘활용해서 피보나치 행렬로 풀어봤습니다. 저번의 코드보다 시간복잡도가 훨씬 줄어든 거 같은데 틀렸다고 뜨네요

혹시 여기서 어느 부분이 틀렸는지 짐작가는 부분이 있나요??? 오버플로우 문제인가요??

#include <iostream>
using namespace std;

typedef struct matrix{
	unsigned long long int mat[2][2];
}Matrix;

Matrix I = {1,1,1,0};

Matrix Power_Matrix(unsigned long long int a){
	if(a==1)return I;
	Matrix tmp;
	Matrix m;
	Matrix m1;
	
	if(a%2==0){
		tmp=Power_Matrix(a/2);
		m.mat[0][0]=((tmp.mat[0][0]*tmp.mat[0][0]%1000000000)+(tmp.mat[0][1]*tmp.mat[1][0]%1000000000))%1000000000;
		m.mat[0][1]=((tmp.mat[0][0]*tmp.mat[0][1]%1000000000)+(tmp.mat[0][1]*tmp.mat[1][1]%1000000000))%1000000000;
		m.mat[1][0]=((tmp.mat[1][0]*tmp.mat[0][0]%1000000000)+(tmp.mat[1][1]*tmp.mat[1][0]%1000000000))%1000000000;
		m.mat[1][1]=((tmp.mat[1][0]*tmp.mat[0][1]%1000000000)+(tmp.mat[1][1]*tmp.mat[1][1]%1000000000))%1000000000;
	}
	else{
		tmp=Power_Matrix((a-1)/2);
		m.mat[0][0]=((tmp.mat[0][0]*tmp.mat[0][0]%1000000000)+(tmp.mat[0][1]*tmp.mat[1][0]%1000000000))%1000000000;
		m.mat[0][1]=((tmp.mat[0][0]*tmp.mat[0][1]%1000000000)+(tmp.mat[0][1]*tmp.mat[1][1]%1000000000))%1000000000;
		m.mat[1][0]=((tmp.mat[1][0]*tmp.mat[0][0]%1000000000)+(tmp.mat[1][1]*tmp.mat[1][0]%1000000000))%1000000000;
		m.mat[1][1]=((tmp.mat[1][0]*tmp.mat[0][1]%1000000000)+(tmp.mat[1][1]*tmp.mat[1][1]%1000000000))%1000000000;	
		m1=m;
		m.mat[0][0]=((m1.mat[0][0]*I.mat[0][0]%1000000000)+(m1.mat[0][1]*I.mat[1][0]%1000000000))%1000000000;
		m.mat[0][1]=((m1.mat[0][0]*I.mat[0][1]%1000000000)+(m1.mat[0][1]*I.mat[1][1]%1000000000))%1000000000;
		m.mat[1][0]=((m1.mat[1][0]*I.mat[0][0]%1000000000)+(m1.mat[1][1]*I.mat[1][0]%1000000000))%1000000000;
		m.mat[1][1]=((m1.mat[1][0]*I.mat[0][1]%1000000000)+(m1.mat[1][1]*I.mat[1][1]%1000000000))%1000000000;
	}
	return m;
}

int main (){
	unsigned long long int a,b;
	Matrix M1,M2;
	cin>>a>>b;
	M1=Power_Matrix(a+1);
	M2=Power_Matrix(b+2);
	cout<<M2.mat[0][1]-M1.mat[0][1]<<endl;
	return 0;
}

kcl5363 6년 전 0

해결했습니다~~ 감사합니다!! ^^

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

2086 시간초과

kcl5363 6년 전 0

jh05013 6년 전 0

kcl5363 6년 전 0

jh05013 6년 전 0

Green55 6년 전 0

kcl5363 6년 전 0

kcl5363 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말