글 읽기 - 행렬제곱 시간초과..

astrohsy 8년 전 0

b가 매우 커질 때, 무식하게 다 따라가가지고 시간초과 나는 것은 알겠는데..

그 방법 말고, 어떻게 접근할 수 있지는지 힌트 좀 부탁드립니다. ㅠㅠ

#include <iostream>
using namespace std;

int main()
{
    long cnt;
    long b;
    int p_sum;
    int value;
    
    int matrix[5][5];
    int result[5][5];
    int temp[5][5];
    
    cin>>cnt; cin>>b;
    
    for(int i = 0; i<cnt; i++)
    {
        for(int j=0; j<cnt; j++)
        {
            cin>>value;
            result[i][j] = value;
            matrix[i][j] = value;
        }
    }
    
    for(int t=0; t<b-1; t++)  //제곱
    {
        memcpy( temp, result, 5*5*4);
        
        for(int i=0; i<cnt; i++)
        {
            for(int j=0; j<cnt; j++)
            {
                p_sum = 0;
                
                for(int k=0; k<cnt; k++)
                     p_sum += temp[i][k] * matrix[k][j];
                
                result[i][j] = p_sum % 1000;
            }
        }
    }
    
    for(int i = 0; i<cnt; i++)
    {
        for(int j=0; j<cnt; j++)
            cout<<result[i][j]<<" ";
        
        cout<<endl;
    }
}

kesakiyo 8년 전 5

Square and Multiply 를 사용하면 매우 큰 수의 거듭제곱에 대해서 효율적으로 계산할 수 있습니다.

예를 들어 a^10 이라는 수가 있다고 가정해보져

그러면 보통 a*a*a*a*a*a*a*a*a*a 이렇게 계산을 하는데 n이 작으면 잘 동작하겠지만

n이 막 10억 100억 이러면 시간내에 들어올 수가 없죠.

그러면 a^10을 조금 바꿔볼께요. 10을 2진수로 표현을 하게되면 1010(2) 가 나오게 됩니다.

이걸 이용해서 a^10을 다시 표현을 해 볼게요

a^2 * a^8 = a^10 이라는 결과를 도출할 수 있고

결과적으로 a^1, a^2, a^4, a^8 ..... 을 이용해서 모든 a^n 을 빠르게 계산할 수 있습니다.

시간복잡도는 O(n) 에서 O(logn) 으로 줄어들게 되고요.

뭔가 빠르게 넘어간거 같지만 잘 생각해보면 알 수 있을꺼에요!!

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

문제

문제

출처

ICPC

행렬제곱 시간초과..

astrohsy 8년 전 0

kesakiyo 8년 전 5

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말