백준 - 10830(재귀, 분할정복)

import sys

def f_gob(arr):
    ans = [0]*n
    temp = [0]*n
    for i in range(n):
        for j in range(n):
            t = 0
            for k in range(n):
                t = t + int(arr[i][k]) * int(matrix[k][j])
            temp[j] = int(t)
        ans[i] = temp
        temp = [0]*n

    global key_cnt
    key_cnt = key_cnt +1

    s=""
    if key_cnt == key:
        for i in ans:
            for j in i:
                s = s + str(j % 1000) + ' '
            s = s + '\n'
        print(s)
    else:
        f_gob(ans)


def gob(arr):

    ans = [0]*n
    temp = [0]*n
    for i in range(n):
        for j in range(n):
            t = 0
            for k in range(n):
                t = t + int(arr[i][k]) * int(arr[k][j])
            temp[j] = int(t)
        ans[i] = temp
        temp = [0]*n

    global cnt
    global key
    cnt = cnt+1

    s =""
    if b - 2**(cnt) == 0:
        for i in ans:
            for j in i:
              s = s + str(j % 1000)
            s = s + '\n'
        print(s)

    elif b - 2 ** (cnt) >0 and b-2**(cnt +1) < 0:
        key = b - 2 ** (cnt)
        f_gob(ans) #1승씩 증가

    elif b - 2 ** (cnt) > 0 and b - 2 ** (cnt + 1) > 0:
        gob(ans) #제곱의 제곱




n,b = sys.stdin.readline().split()
n = int(n)
b = int(b)
matrix = []
global cnt
cnt = 0

global key

global key_cnt
key_cnt = 0

for i in range(n):
    matrix.append(sys.stdin.readline().split())

gob(matrix)

우선 최대한 효율적으로 짜기 위해 다음과 같이 했다.

만약에 20번 제곱을 한다 치면 우리는 a^20일 구해야 한다.

내가 만들어놓은 gob()를 이용하면

a^2 -> 재귀 호출 ->  a^4 -> 재귀 호출 -> a^8 -> 재귀 호출 -> a^16 이 된다.

한번 더 하면 20을 넘어 버리기 때문에 여기 까지만 하고 그 후부터는

f_gob()을 호출하면 17,18,19,20 승이 되어서 결과가 나온다.

그렇지만 시간 초과가 난다. 

import sys

def solution(arr1, arr2):
    answer = [ len(arr2[0])*[0] for i in range (len(arr1)) ]
    for i in range (len(answer) ):
        for j in range ( len(answer[i]) ):
            for k in range ( len(arr1[i] ) ):
                answer[i][j] += arr1[i][k] * arr2[k][j]
                answer[i][j] = answer[i][j] % 1000
    return answer

def Multiple(arr,n,x,a):
    global key
    ans = arr
    while 1:
        x = x * 2
        if x > n:
            break
        ans = solution(ans,ans)

    if x >= n:
        x = x // 2
        if x == n:
            key = solution(a,ans)
            return 1
        else:
            a = solution(a,ans)
            Multiple(arr,n-x,1,a)


n,b = map(int,sys.stdin.readline().split())
a = [[0]*n for _ in range(n)]
arr = []
global key
key = 0
for i in range(n):
    arr.append(list(map(int,sys.stdin.readline().split())))
    a[i][i] = 1

Multiple(arr,b,1,a)


for i in key:
    print(*i)

한 자리씩 쪼개는 것으로 성공!!