[Java+Python]10830번, 행렬 제곱

목차

 

분할 정복 단계

 

[Java+Python]2630번, 색종이 만들기

[Java+Python]1992번, 쿼드 트리

[Java+Python]1780번, 종이의 개수

[Java+Python]1629번, 곱셈

[Java+Python]11401번, 이항 계수 3

[Java+Python]2740번, 행렬 곱셈

[Java+Python]11444번, 피보나치 수 6

[Java+Python]6549번, 히스토그램에서 가장 큰 직사각형

 

문제

 

크기가 N*N인 행렬 A가 주어진다. 

이때, A의 B제곱을 구하는 프로그램을 작성하시오. 

수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.

 

입력

 

첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤  5, 1 ≤ B ≤ 100,000,000,000)

둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.

 

출력

 

첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다.

 

풀이

 

이전에 풀었던 <1629번 - 곱셈>, 즉 고속 거듭제곱 문제의 행렬 버전이다.

 

[Java+Python]1629번, 곱셈

[Java+Python]1629번, 곱셈

 

거듭제곱이 가능하기 위해서는 반드시 정사각행렬이어야 하므로 문제 조건의 근거가 된다.

 

직전 문제인 <2740번 - 행렬 곱셈>을 함께 사용해서 다음과 같이 분할정복 기법을 사용할 수 있다.

 

[Java+Python]2740번, 행렬 곱셈

[Java+Python]2740번, 행렬 곱셈

 

1. n과 b를 입력받아 n*n 배열(리스트) A를 초기화한다. 이 과정에서도 값이 클 수 있으므로 1000으로 나눈 나머지를 입력한다.
2. 고속 거듭제곱을 위한 pow() 메서드를 호출한다. 이 메서드는 아래와 같이 동작한다.
   
   
   1. exponent가 1이면 A를 그대로 반환한다.
   2. pow() 메서드를 재귀호출해 A를 (exponent / 2)번 거듭제곱한 결과를 구한다.
   3. 이 과정에서 행렬 곱셈을 위한 메서드 multiply() 메서드를 호출하는데,
      해당 메서드는 행렬 곱셈을 진행하며 값을 1000으로 나눈 나머지를 저장한다.
3. pow()의 최종 결과를 이차원 배열(리스트) result에 입력한다.
4. 이중 반복문을 돌며 결과를 출력한다.

알고리즘에서 볼 수 있듯이 위에 언급한 두 문제를 풀고 이해했다면 그다지 어려울 것 없는 문제라고 할 수 있다.

 

Java

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Prob10830 {

	static int n;
	static long b;
	static int[][] A;
	static int p = 1000;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		n = Integer.parseInt(st.nextToken());
		b = Long.parseLong(st.nextToken());
		A = new int[n][n];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < n; j++) {
				A[i][j] = Integer.parseInt(st.nextToken()) % p;
			}
		}

		int[][] result = pow(A, b);

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				System.out.print(result[i][j] + " ");
			}

			System.out.println();
		}

	}

	public static int[][] pow(int[][] A, long exponent) {

		if (exponent == 1L) {
			return A;
		}

		int[][] temp = pow(A, exponent / 2);
		temp = multiply(temp, temp);

		if (exponent % 2 == 1) {
			temp = multiply(temp, A);
		}

		return temp;
	}

	public static int[][] multiply(int[][] A, int[][] B) {

		int[][] C = 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++) {
					C[i][j] += (A[i][k] * B[k][j]) % p;
				}
				C[i][j] %= p;
			}
		}

		return C;
	}
}

 

Python

 

import sys

n, b = map(int, sys.stdin.readline().rstrip().split())
p = 1000
A = [[int(x) % 1000 for x in sys.stdin.readline().rstrip().split()] for _ in range(n)]


def multiply(A, B):
    global n
    C = [[0 for _ in range(n)] for _ in range(n)]

    for i in range(n):
        for j in range(n):
            for k in range(n):
                C[i][j] += (A[i][k] * B[k][j]) % p
            C[i][j] %= p
    return C


def pow(A, exponent):
    if exponent == 1:
        return A

    temp = pow(A, exponent // 2)
    temp = multiply(temp, temp)

    if exponent % 2 == 1:
        temp = multiply(temp, A)

    return temp


result = pow(A, b)

for i in result:
    print(' '.join(map(str, i)))

 

Performance