10830 백준 파이썬

행렬 곱셈 이해하는데 시간이 걸렸던 문제... 

교육과정에 행렬이 없어서 마주했을때 당황했다.

1 2 

3 4 를 제곱했는데 왜 저렇게 되지?

이 생각을 했다.

 

이 문제를 통해 알 수 있었던 것은 나는 반복문 이해도가 꽤나 떨어지는 편이라는 것이다.

2중까진 가능한데 3중부터 영 별로다. 그래서 플로이드 와샬도 거의 암기식으로 외웠다가 최근에 왜 경유점이 반복문 밖에 존재하는지 이해했다.

 

분할 정복을 통해서 해결했다. 

n,t=map(int,input().split())
orgin=[]
for _ in range(n):
    orgin.append(list(map(int,input().split())))

def multiple(m1,m2):
    res=[[0 for _ in range(n)] for _ in range(n)]
    for t in range(n):
        for x in range(n):
            for y in range(n):
                res[t][x]+=m1[t][y]*m2[y][x]
            res[t][x]=res[t][x]%1000
    return res

def bin(t,orgin):
    if t==1:
        return orgin
    elif t==2:
        return multiple(orgin,orgin)
    else:
        tmp=bin(t//2,orgin)
        if t%2==0:
            return multiple(tmp,tmp)
        else:
            return multiple(multiple(tmp,tmp),orgin)

res=bin(t,orgin)
for x in res:
    for y in x:
        print(y%1000, end=' ')
    print()