[백준 10830] 행렬 제곱

[BanApp]

import sys
def solution(arr1, arr2):
    answer = [ len(arr2[0])*[0] for i in range (len(arr1)) ]
    for i in range (len(answer) ):
        for j in range ( len(answer[i]) ):
            for k in range ( len(arr1[i] ) ):
                answer[i][j] += arr1[i][k] * arr2[k][j]
                answer[i][j] = answer[i][j] % 1000
    return answer

def Multiple(arr,n,x,a):
    global key
    ans = arr
    while 1:
        x = x * 2
        if x > n:
            break
        ans = solution(ans,ans)

    if x >= n:
        x = x // 2
        if x == n:
            key = solution(a,ans)
            return 1
        else:
            a = solution(a,ans)
            Multiple(arr,n-x,1,a)


n,b = map(int,sys.stdin.readline().split())
a = [[0]*n for _ in range(n)]
arr = []
global key
key = 0
for i in range(n):
    arr.append(list(map(int,sys.stdin.readline().split())))
    a[i][i] = 1

Multiple(arr,b,1,a)


for i in key:
    print(*i)

이것도 백준 시작한지 얼마 안됐을때 도전했다가 포기했던 문제다.
오늘 이거 풀면서 맞왜틀(심한말) 많이 했다.
우선 solution 함수는 단순하게 반복문을 이용해서 크기가 두 행렬의 곱을 해주는 함수이다.
multiple은 제곱을 수행하는 함수 이다. 대략적인 아이디어는 이렇다.
만약에 우리가 A라는 행렬의 100승이 궁금하다고 하자.
그럼 우선 100에 가장 가까운 2의 제곱을 찾는다. 2^1 =2, 2^2=4, 4^2=16, 16^2 = 64
4번째로 나오는 수가 100에 가장 가까운 2의 제곱이다.
위 과정을 수행함과 동시에 solution 함수도 같이 굴려준다.
solution(A,A), solution(A^2,A^2), solution(A^4,A^4), solution(A^8,A^8) == A^16 ... A^64 이다.
최종적으로 나온 A^64는 ans에 저장해준다.
이를 a를 통해서 다음 재귀로 넘겨준다. 따라서 첫 a는 단위행렬 함수가 되어야한다.
다음으로 100-64 = 36이다. 또 36에 가장 가까운 2의 제곱을 계속 재귀적으로 찾는다.
그러면서 2의 제곱 탐색이 멈출때 마다 ans에 곱해준다.
그러면 A^64 * A^32 + A^4 = A^100 이다.
100 - 64 - 32 -4 를 해가면서 x==n 이 되는 순간 최종적으로 행렬곱(and)을 key에 저장해주고 return 1을 통해서 함수를 종료한다.
아이디어도 금방 떠올랐고 구현도 어렵지 않았지만 계속 메모리초과 와 시간초과의 늪에 빠졌는데 이유는 다음과 같았다.

나는 최종적으로 연산된 key리스트 안의 원소들을 하나하나 1000으로 나눠 나머지를 출력해주려고 했다.
다만 이렇게 되면 문제에서 제한된 b의 숫자가 굉장히 큰데 1000^10000000000 이런 숫자가 나왔다가는 무조건 메모리 초과가 난다.
문득 이런 생각이들어서 문제를 다시읽어봤다. "행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다."
만약 N제곱이 됐더라도 행렬안의 각 원소들의 값은 1000을 넘으면 안되는 것이였다.
따라서 solution 함수의 return 전에 각 원소를 1000으로 나눠 주는 과정을 넣어주니깐 바로 통과...
여러분 항상 문제는 잘 읽고 문제를 완전하게 이해하고 푸는것이 중요합니다..

2달전에 시도했던 풀이 보니깐 재귀를 두려워 했던 저는 단순 반복문을 통해서 풀려고 시도했던 자신을 보고 반성했습니다.
하지만 아직도 N-Queen 못품^_^ N-Queen 풀기 싫어서 다른 문제 먼저 풀고있는데 너무 재밌네요^^