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

10830번: 행렬 제곱

 

백준 2740번 : 행렬 곱셈을 응용한 문제이다. 

B의 범위가 매우 크기 때문에 단순히 2740번 문제에서 for문을 하나 더 추가해서 문제를 풀면 시간초과가 난다. 

 

이 문제는 행렬을 곱하는 똑같은 과정을 반복하기 때문에 이미 한번 계산한 결과는 다시 재사용하면 계산 횟수를 줄일 수 있다. 따라서 분할과 정복 방법으로 문제를 해결하였다.

 

만약 B가 짝수라면, B번 행렬을 곱한 결과는 B/2번 행렬을 곱한 결과 * B/2번 행렬을 곱한 결과가 된다.

이 때 B/2번 행렬을 곱한 결과는 한 번만 계산한 뒤, 두 번 곱해주면 된다.

 

B/2번 행렬을 곱한 결과는 B/4번 행렬을 곱한 결과 * B/4번 행렬을 곱한 결과가 된다.

이 때도 마찬가지로 B/4번 행렬을 곱한 결과는 한 번만 계산하면 된다.

 

만약 B가 홀수라면, B번 행렬을 곱한 결과는 B/2번 행렬을 곱한 결과 * (B/2+1)번 행렬을 곱한 결과가 된다.

이 때 B/2번 행렬을 곱한 결과(res)는 한 번만 계산한 후, res*res*A를 하면 된다.

 

 

전체 코드 :