[BOJ][Python]10830 풀이

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

10830번: 행렬 제곱

def matmul(mat1, mat2):
    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] += mat1[i][k] * mat2[k][j]
            result[i][j] %= 1000
    return result

n, b = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
ans = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    ans[i][i] = 1
while True:
    if b == 0:
        break
    if b % 2 == 1:
        ans = matmul(a, ans)
    a = matmul(a, a)
    b //= 2
for i in ans:
    print(*i)

지난 번에 피보나치 6번 문제의 핵심이 이것과 완벽하게 동일했죠. 그 때 못풀어서 이리저리 풀이를 찾아봐서 그런가 이번에는 보자마자 바로 풀었네요.

 

해당 문제는 컴퓨터의 연산량 측면에서 볼 때 작은 수를 몇백번 곱하는 것보다 큰 수를 몇 번만 곱하는게 더 연산량이 작다는 점이 핵심입니다. 예를 들어 2의 1024승을 구하는 문제라고 치면, 2를 1024번 곱하고 있을 게 아니라 2의 512승을 제곱하는게 연산량이 작다는 말이죠(실제로는 큰 수를 연산할 때 작은 수보다 시간이 더 오래걸려서 런타임의 감소가 완전히 비례하지는 않습니다).

 

그래서 위 문제도 b가 1e11까지 입력이 들어올 수 있기 때문에 이런식으로 차라리 밑을 키우고 지수를 줄이는 분할정복을 사용해서 풀게됩니다. numpy에는 행렬 연산을 지원하지만 기본 파이썬은 지원하지 않으니까 행렬 곱셈 함수를 따로 만들어서 사용해주시면 되겠습니다.

 

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

11444번: 피보나치 수 6

비슷한 문제를 연습해보고 싶으시다면 이 문제를 추천드립니다. 피보나치 수에 대한 이해가 필요하지만 풀이의 핵심은 동일합니다.