행렬 제곱 [백준 10830] - python

import sys
input = sys.stdin.readline

def BOJ10830() :
  N, B = map(int, input().split())

  def matrix_mul(a, b) :
    result = [[0 for _ in range(N)] for _ in range(N)]
    
    for i in range(N):
      for j in range(N):
        for k in range(N):
          result[i][j] += (a[i][k] * b[k][j]) % 1000
    
    for i in range(N) :
      for j in range(N) :
        result[i][j] %= 1000

    return result
  
  def divide(a, count) :
    if count == 1 :
      return a
    tmp = divide(a, count // 2)
    if count % 2 == 1 :
      return matrix_mul(matrix_mul(tmp, tmp), a)
    else :
      return matrix_mul(tmp, tmp)

  array = []
  for _ in range(N) :
    array.append(list(map(int, input().split())))

  answer = divide(array, B)

  for i in range(N) :
    for j in range(N) :
      print(answer[i][j] % 1000, end = " ")
    print()

BOJ10830()

 

접근방법 : 

1. B의 범위가 굉장히 커서 제곱을 해줄때 O(N)의 시간 복잡도가 발생해서 무조건 시간 초과다
거듭제곱의 분할 정복 방식으로 접근해야 한다(divide 함수 부분)

 

장애물이였던 것: 

1.  행렬의 계산을 나타내는 것에서 굉장히 애를 먹었다. 머리가 막힐때는 직접 손으로 적어보고 먼저 흐름을 단순히 구현해보자

 

 

https://www.acmicpc.net/problem/10830

10830번: 행렬 제곱