[C언어] 11726번 2×n 타일링 - DP, 행렬

#include <stdio.h>

long long int arr[10000000];

long long int f(long long int n) {
    long long int a, b;
    
    if(n<=1)
        return 1;
        
    if(n<10000000) {
        if(arr[n])
            return arr[n];
        
        if(n%2) {
            a=(n+1)/2;
            b=a-1;
        }
        else
            a=b=n/2;
        
        return arr[n] = ((f(a)*f(b))%10007 + (f(a-1)*f(b-1))%10007)%10007;
    }
    else {
        if(n%2) {
            a=(n+1)/2;
            b=a-1;
        }
        else
            a=b=n/2;
        
        return ((f(a)*f(b))%10007 + (f(a-1)*f(b-1))%10007)%10007;
    }
}

int main()
{
    long long int n;
    
    scanf("%lld", &n);
    printf("%lld", f(n));
    
    return 0;
}

 

원래 이 문제의 출제자는 DP로 푸는 것이겠지만 이 문제에서 출력 값은 선형 점화식으로 나타낼 수 있기 때문에 행렬 거듭제곱으로 훨씬 더 빠른 시간 내에 답을 구할 수 있다. 물론 이 문제에서는 그럴 필요가 없지만. 아무튼 그래서 나는 행렬곱으로 풀었다.

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.