상세 컨텐츠

본문 제목

백준 행렬 제곱 파이썬

프로그래밍/백준풀이

by 아싸호랑나비 2022. 12. 18. 18:03

본문

제곱시키는 문제 B의 범위가 매우크다 1 ≤ B ≤ 100,000,000,000

 

내코드의 작동방식은 다음과 같다 

행렬의 곱셈을 B번만큼 하는것이다 다만 보면 B가 무려 천억이라는 말도안되는 숫자를 가지고있어서

코드를 짜면서도 분명히 시간초과가 될것이라고 예상했고 그것은 사실이었다

제출해보니 역시 예상대로 0%도 넘기지 못하고 시간초과되었다

 

만약 B번만큼 연산을 반복하는게 아니라면 어떤 규칙이 있는것일까

직접 확인해보도록 한다

 

잠깐 혹시 이게 통하는지 궁금해졌다

그러니까 

행렬 

1 2

3 4

의 제곱끼리 곱했을때

행렬 

1 2 

3 4

의 4제곱이 나오는지 말이다

만약 이게 된다면 

 

시간을 절약 할수있을것이다

된다

 

그렇다면 행렬 제곱이었던것을 쪼갤수있을것이다

 

그렇게 해서 제출했는데시간초과가떳다

아차차

저장기능을 활용해서 다시 제출하니 이번엔 맞았다

# 행렬 제곱
d={}
def mod(a,b):
    return (a*b)%1000

def multiply(array_A,array_B): # 행렬곱을 하는 함수: 두 행렬을 입력값으로 받아 결과를 제출
    big_array=[] 
    for i in range(N):
        array=[]
        for j in range(N):
            sumed=0
            for k in range(N):
                sumed+=mod(array_A[i][k],array_B[k][j])
            array.append(sumed%1000)
        big_array.append(array)
    return big_array

def divide(matrix,B):
    # print(B)
    try:
        return d[B]
    except: 
        if B==1:
            d[B]=matrix
            return d[B]
        else:
            dd=B//2
            d[B]=multiply(divide(matrix,dd),divide(matrix,B-dd))
            return d[B]

N,B=map(int,input().split())
array_A=[]
for i in range(N):
    array_A.append([i%1000 for i in list(map(int,input().split()))])

# sumed=array_A
# for i in range(1,B):
#     sumed=multiply(sumed,array_A)
result=divide(array_A, B)

for i in result:
    print(*i)

 

'프로그래밍 > 백준풀이' 카테고리의 다른 글

히스토그램에서 가장 큰 직사각형  (0) 2023.01.08
피보나치수 6 파이썬  (0) 2022.12.24
이항계수3 파이썬  (0) 2022.12.11
알고리즘 수업 - 병합 정렬 1 파이썬 풀이  (0) 2022.10.28
주가 예측 5  (0) 2022.10.14

관련글 더보기