[Python 파이썬]백준 10830번 행렬 제곱 풀이

문제

문제는 정말 간단하다.
그냥 주어지는 행렬의 B제곱만 구하면 되는 일

말이 간단하지만 입력은 1000억까지다.
입력이 굉장히 크기도하고, 제곱이면 분할정복으로 접근할 수 있지 않을까..? 라는 생각으로 접근한다면

거듭제곱 분할정복으로 모두 쉽게 풀지 않을까 싶으나
80%에서 뭐가 틀렸을까 계속 고민하게 만드는 문제랄까..,

풀이

1. 첫 번째는 행렬을 곱하는 함수를 만들자.

어쨋건 행렬을 곱해야하니 행렬을 곱하는 함수를 하나 정의해주자.

def multiply(matrix1, matrix2):
    global n
    result = []
    for i in range(n):
        result2 = []
        for j in range(n):
            value = 0
            for t in range(n):
                value += matrix1[i][t] * matrix2[t][j]
            result2.append(value % 1000)
        result.append(result2)
    return result

행렬은 총 계산이 (행렬 크기)^3 번일어나니까 가볍게(?) for문 3개로 처리해주자.
아 문제에서 1000으로 나눈 나머지를 출력하랬으니 % 1000을 계속 해줘야한다.
(결과에서만 나누면.., 숫자가 너무 커져서 실행이 안 돼..,)

2. 두 번째는 거듭제곱을 하는 함수를 만들자.

지수 거듭제곱 분할정복 함수는 많이 써봤으니까..!(피보나치 풀 때도 그렇고)

def power(matrix, exponent):
    if exponent <= 1:
        return matrix
    else:
        if exponent % 2 == 0:
            new_exponent = power(matrix, exponent // 2)
            return multiply(new_exponent, new_exponent)
        else:
            new_exponent = power(matrix, exponent // 2)
            return multiply(multiply(new_exponent, new_exponent), matrix)

다만, 정수와는 다르게 기본 값을 행렬로 주는거..!
그리고 new_exponent 계산할 때, integer division 쓰는 거..,

이제 입력만 받고 함수에만 넣으면 뚝딱이다.

그러나, 80%의 장벽에서 막히고 마는데..,,,

결국 테케 막 입력해보다가

행렬 원소가 1000이고 B가 1일 때, 1000으로 나눈 나머지를 출력하면 0이 나와야하는데,
B가 1일 때, 함수 호출을 안 하고 그냥 출력하니 1000이 그대로 나와서 틀렸던거..,

아무튼 이 부분만 보완하면 무난히 클리어 된다..!

코드

def multiply(matrix1, matrix2):
    global n
    result = []
    for i in range(n):
        result2 = []
        for j in range(n):
            value = 0
            for t in range(n):
                value += matrix1[i][t] * matrix2[t][j]
            result2.append(value % 1000)
        result.append(result2)
    return result


def power(matrix, exponent):
    if exponent <= 1:
        return matrix
    else:
        if exponent % 2 == 0:
            new_exponent = power(matrix, exponent // 2)
            return multiply(new_exponent, new_exponent)
        else:
            new_exponent = power(matrix, exponent // 2)
            return multiply(multiply(new_exponent, new_exponent), matrix)


n, k = map(int, input().split())
mat = [list(map(int, input().split())) for _ in range(n)]

if k == 1:
    for i in range(n):
        for j in range(n):
            mat[i][j] = mat[i][j] % 1000
    z = mat
else:
    z = power(mat, k)

for x in range(n):
    print(*z[x])

끝!