10830번 행렬 제곱

문제

 

 

---

 

문제풀이

 

먼저 행렬의 곱 부터 알아보자!!

3 X 3 행렬의 경우 행렬의 곱은 위 사진과 같이 진행된다. 

 

즉 행렬의 제곱이라면

	public static int[][] multiplyMatrix(int[][] a, int[][] b) {
		int[][] res = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				for (int k = 0; k < n; k++) {
					res[i][j] += (a[i][k] * b[k][j]) % 1000;
					res[i][j] %= 1000;
				}
			}
		}
		return multiplyMatrix(res,b);

 

이런 식으로 진행 한 뒤 그 결과와 원래 배열을 다시 메서드로 넣어 제곱 횟수만큼 반복하면 된다!

 

하지만 이 경우 4중 포문으로 어마어마한 시간이 소요된다. 따라서 정복 분할 방식을 사용하자!

 

	public static int[][] matrixPower(int[][] matrix, long exp) {
		int[][] result = new int [n][n];
		for (int i = 0; i < n; i++) {
			result[i][i] = 1;
		}

		while (exp > 0) {
			if (exp % 2 == 1) {
				result = multiplyMatrix(result, matrix);
			}
			matrix = multiplyMatrix(matrix, matrix);
			exp /= 2;
		}

		return result;
	}

 

홀수인 경우에만 단위 행렬을 통해 처리하고 짝수의 경우 거듭 제곱의 형태로 처리한다!

비록 힌트는 봤지만 분할 정복에선 행렬 문제가 참 많고 어려운 것 같다!