[Python][백준] 10830. 행렬 제곱 / 분할정복 (G4)

🔗링크 :  

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

---

🗒️파이썬 코드 풀이

import sys

sys.setrecursionlimit(100000) 

N,B = map(int,sys.stdin.readline().split())

A = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]

def mul_matrix(mat1,mat2):
    res = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            for k in range(N):
                res[i][j] += mat1[i][k] * mat2[k][j]
            res[i][j] %= 1000 
    return res

def divided(n,a,b):
    if b == 1 :
        return a
    elif b == 2 :
        return mul_matrix(a,a)
    else:
        temp = divided(n,a,b//2)
        if b%2 == 1:
            return mul_matrix(mul_matrix(temp,temp),a)
        else :
            return mul_matrix(temp,temp)
    


ls = divided(N,A,B)
for i in range(len(ls)):
    for j in range(len(ls)):    
        print(ls[i][j]%1000,end =" ")
    print()

 

1. 이 문제에서 묻고자 하는 것은 크게 2개이다. 

( 행렬 곱을 구현 할 수 있는지 ? / 분할 정복을 할 수 있는지 ? )

 

2. N이 어떤게 나올지 모르니, 어떻게 해서든 일반화를 시켜야한다.

행렬 제곱 같은 경우, 직접 써보고 어떤식으로 i, j, k를 구성할지 생각해야한다.

예시) 2 * 2 행렬 
00 * 00 + 01*10          00 * 01 + 01*11
10 * 00 + 11*10          10 * 01 + 11*11

행렬 곱을 하면 해당 형식으로 나온다.  

2*2 행렬 경우 연산을 2^3 만큼 해야하니, 3개의 for 문을 예상한다.

 

(1)

00 * 00 + 01*10 부분을 보면,        

00 * 00 + 01*10에서 1로 된 값들이 k임을 예상 할 수 있다.

→ [?][k] * [k][?]

 

(2)

00 * 01 + 01*11의 부분을 보면,

00 * 01부분이 바뀌었으니 1로 된 부분이 j가 되고,

→ [?][k] * [k][j]

 

(3)

10 * 00 + 11*10  의 부분을 보면,

맨 앞에 부분이 0에서 1이 되었으니 i 가 된다.

→ [i][k] * [k][j]

 

3. 행렬 제곱을 구하고 % 1000을 해준다. 

(안할 경우 시간초과)

 

4. 이후 분할 정복으로 원하는 행렬 제곱을 구해준다. 

- b가 1인 경우  a를 반환

- b가 2인 경우  a의 제곱을 반환

재귀 호출 후 리턴되는 값들을 또 제곱해서 B 제곱까지 구해준다.

(홀수와 짝수인 경우를 나눠야한다.)

 

 

📌  문제 코멘트

우선 행렬 제곱 구하는 함수도 못 구했었다.

나는 이렇게 인덱싱하는 문제를 보면 먼저 겁부터 먹는다.

우선 공통점을 찾고 규칙을 찾아 해결해보자.

 

그리고 해당 문제에서 나는 재귀함수로 B 만큼 제곱을 해주었는데,

시간 초과가 발생했다.

 

B제곱을 나누기 2 하여 분할하는 방식도 기억해두자.

---

 

📚문제

크기가 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제곱한 결과를 출력한다.

예제 입력 1 복사

2 5
1 2
3 4

예제 출력 1 복사

69 558
337 406

예제 입력 2 복사

3 3
1 2 3
4 5 6
7 8 9

예제 출력 2 복사

468 576 684
62 305 548
656 34 412

예제 입력 3 복사

5 10
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1

예제 출력 3 복사

512 0 0 0 512
512 0 0 0 512
512 0 0 0 512
512 0 0 0 512
512 0 0 0 512