[PYTHON] 백준 10830 - 행렬 제곱

성능 요약

메모리: 114488 KB, 시간: 124 ms

분류

분할 정복, 분할 정복을 이용한 거듭제곱, 선형대수학, 수학

문제 설명

크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.

입력

첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000)

둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다.

---

아이디어, 문제풀이

• 행렬의 곱을 어떻게 표현할건지?
• b를 짝수, 홀수로 나누어 분할정복이 가능하게끔 해야한다.
• 행렬이 1000이 넘어갈때의 출력값은 1000을 나눈 나머지로 나올수 있도록 해야한다.

---

TROUBLE SHOOTING

• 문제 자체는… 어렵다기보단 잔인했다. 실제로 팀원들과 리뷰를 할때, 행렬의 곱 자체가 어떻게 이루어지는지 부터가 이 문제의 해결과제 였던것 처럼, 기본적으로 알아야하는게 많았던 문제라고 생각한다.

• 나도 실제로 행렬곱 연산 함수는 다른 자료들을 참고해 가져왔다. 마찬가지로 제곱근 곱셈을 분할정복 하는 아이디어도 앞선 문제들에서 얻었다. 아래는 혹시나 도움 될까해서, 가공되지 않은 행렬곱 함수를… 올립니다.

  def mult(A, B):
      result = [[0] * (len(B[0])) for _ in range(len(A))]
      for i in range(len(A)):
          for j in range(len(B[0])):
              for k in range(len(B)):
                  result[i][j] += A[i][k] * B[k][j]
      return result

  2 * 2 뿐 아니라 모든 행렬에서 적용이 가능하다. 대신 행렬의 곱 연산법칙을 만족해야함!
  

• 가장 해맸던 파트는 아래코드다.

  if b == 1:
          return a_list

  이 코드덕분에 90%까지 가다가 계속 틀렸는데, 이유는 저어어어어엉말 간단하다. 바로, 한개의 행렬을 출력할땐, mult연산이 진행되지 않아 1000으로 나누지 않는다는것… 말그대로 b=1일때는 전부다 1000이상의 수로 출력됐을거라는 것이다. 예제를 좀더 넣어보고 해봤어야했는데, 정말 전혀 생각하지 못했다.. 정말 많은 시간을 여기에 사용했다 ;ㅁ; 아래 코드처럼 직접 나누어 줘야 한다.

  if b == 1:
          for i in range(n):
              for j in range(n):
                  a_list[i][j] %= 1000
          return a_list

---

코드

#https://www.acmicpc.net/problem/10830
#행렬 제곱
#10830

import sys
input = sys.stdin.readline

n, b = map(int, input().split())
b = int(b)
a_list = []
for i in range(n):
    a = list(map(int, input().split()))
    a_list.append(a)

# print(a_list)

def mult(A, B):
    result = [[0] * (len(B[0])) for _ in range(len(A))]
    for i in range(len(A)):
        for j in range(len(B[0])):
            for k in range(len(B)):
                result[i][j] += A[i][k] * B[k][j]
                result[i][j] %= 1000
    return result

# print(mult(a_list, a_list))

def fun(a_list, b):

    if b == 0:
        # return the identity matrix
        return [[int(i == j) for j in range(n)] for i in range(n)]

    if b == 1:
        for i in range(n):
            for j in range(n):
                a_list[i][j] %= 1000
        return a_list
    
    elif b % 2 == 0:
        recursion = fun(a_list, b//2)
        return mult(recursion,recursion)

    else:
        recursion = fun(a_list, b//2)
        return mult(mult(recursion,recursion), a_list)
    
result = fun(a_list, b)

for i in range(n):
    for j in range(n):
        print(result[i][j], end= " ")
    print()