(Python/🥇4)백준알고리즘 10830번: 행렬 제곱

 

문제 바로가기 

백준 알고리즘 행렬 제곱

 

문제:

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

 

풀이: 

이 전 문제에서 사용한 행렬의 곱을 구하는 방식과, 1629번 곱셈 두개를 사용하는 문제이다.

옛날에 풀었어서 그냥 처음 푸는것 같고 재귀 쓰는거 너무 어렵다. 재귀적으로 생각하는 습관을 가져야하는데 하나하나 들어가서 파악을 하려고 한다. 이러면 안 좋고 그냥 던져준다. 이렇게 이해를 해야하는데, 아직은 안된다. 재귀 관려 많은 문제를 풀어봐야겠다.

 

일단 행렬의 곱을 구하는 방법은

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

N, M = map(int,sys.stdin.readline().split(" "))
arr = [list(map(int,sys.stdin.readline().rstrip().split(" "))) for _ in range(N)]

def solution(arr,M):
    if M == 1: # 베이스 코드
        return arr

    ar = solution(arr, M//2)
    cal = []
    for i in range(N):
        result = []
        for l in range(N):
            a = 0
            for j in range(N):
                a += ar[i][j] * ar[j][l]
            result.append(a%1000)
        cal.append(result)

    answer = []
    if M % 2 == 1:
        for i in range(N):
            result = []
            for l in range(N):
                a = 0
                for j in range(N):
                    a += cal[i][j] * arr[j][l]
                result.append(a%1000)
            answer.append(result)
    else:
        answer = cal
    return answer

for i in solution(arr,M):
    for j in i:
        print(j, end =" ")
    print()

cal 에는 현재 계산한 행렬 값을가져오고

만약 M%2 가 홀수면 1번 더 곱해줘서 answer에 담아 리턴하는 식이다.

 

이 문제랑 이 전 문제 내일 또 풀어보도록 하겠다.