[java] 백준 10830 (행렬 제곱) Gold 4

Problem : https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net Approach 같은 행렬 요소를 여러번 곱하는 문제이므로, 분할 정복을 이용하여 풀 수 있다. 행렬 제곱은 다음과 같이 분할 할 수 있다. 행렬 A의 9제곱을 구한다고 가정했을 때, A^9 = (A^4 * A^4) * A = ((A^2 * A^2) * (A^2 * A^2)) * A 이 된다. 알고리즘 자체는 O(logN)이지만, 행렬 곱셈 자체는 O(N^3)이다. 구현부는 코드와 코드 주석을..