10830번 - 행렬 제곱
분할 정복을 이용해 행렬의 제곱을 구하려고 했는데 시간초과가 나네요...
u는 n*n 크기의 단위행렬을 구한 것이고,
prod 함수는 두 행렬 m1, m2를 곱해주는 함수이고
exp 함수는 행렬 m의 b제곱을 분할 정복을 이용해 구해주는 함수입니다.
도와주세요 ㅠㅠ
메모이제이션을 안하시면, 아무리 재귀로 분할 정복을 해도 선형 오퍼레이션과 비슷하거나 나쁜 퍼포먼스가 나옵니다.
그런데 일반적인 메모이제이션을 사용해도, B값이 10^11까지 가능한데 그 사이 중간값마다 행렬 결괏값을 저장하면 메모리 초과가 뜰 것 같아요.
많이 쓰시는 풀이를 응용해서, (B 이하 가장 큰 2의 제곱수)를 기준으로 메모이제이션을 쓰는 것도 방법이겠죠.
댓글을 작성하려면 로그인해야 합니다.
hwpark12 2년 전
분할 정복을 이용해 행렬의 제곱을 구하려고 했는데 시간초과가 나네요...
u는 n*n 크기의 단위행렬을 구한 것이고,
prod 함수는 두 행렬 m1, m2를 곱해주는 함수이고
exp 함수는 행렬 m의 b제곱을 분할 정복을 이용해 구해주는 함수입니다.
도와주세요 ㅠㅠ