[BAEKJOON] 10830 행렬 제곱

문제 요약

• 알고리즘 분류: 수학, 재귀호출, 분할정복
• 난이도: Gold2
• 문제내용:
  • 행렬의 N 제곱을 구한뒤 각 원소마다 1,000을 나눈 나머지를 구해라.

• 사이트 : https://www.acmicpc.net/problem/11401

10830번: 행렬 제곱

문제풀이

 이번 문제 내용는 2가지만 알면 쉽게 풀수 있다고 생각한다. 첫번째는 행렬 제곱을 처리 하는 방법이다. 행렬 제곱은 행렬 곱셈만 구현 하면 되기 때문에 밑에 사이트에 문제 풀어보거나 복습하면 풀수가 있다.

https://jih3508.tistory.com/68

[BAEKJOON] 2740 행렬 곱셈

 두 번째는 제곱에 대한 처리 방법인데 이번에 지수의 값의 범위가 천억이 들어간다. 그래서 1 ~ 천억까지 O(n)으로 풀기에는 시간상 적합하지가 않다. 통과 하기 위해서는 최소한 O(logN)으로 처리하도록 만들어야 한다. 그 관련해서 처리하는 문제는 아래 사이트에서 확인할수 있으니 문제 풀어보거나 복습하도록 하자.

https://jih3508.tistory.com/24

[BAEKJOON] 1629 곱셈 - Python

1. 행렬 곱셈 처리

 행렬 곱셈 처리 하는 방법은 고등학교 수학에서 나온 개념이다. 모르면 고등학교 수학책에서 행렬에 대한 공부를 하면된다. 그리고 행렬의 곱셈 처리는 아래 코드와 같이 구현 하면된다.

Python

def matrix_multiplication(matrix1, matrix2):
    result = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            for k in range(N):
                result[i][j] += (matrix1[k][j] * matrix2[i][k]) % 1000
    return result

Java

public static int[][] matrix_multiplication(int[][] matrix1, int[][] matrix2){
    int[][] result = 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++) {
                result[i][j] += (matrix1[k][j] * matrix2[i][k]) % 1000; 
            }
            result[i][j] = result[i][j] % 1000;
        }
    }

    return result;
}

 저 위의 코드를 보면 O(n^3)이라는 것을 확인 할수가 있다. 크기가 최대 1000이라서 O(n^3)처리해도 문제가 되지가 않다.

 

2. 분할 곱셈 처리하기

 여기가 위에 보다 생각하기가 쉽지가 않을것이다. 행렬 곱셈은 고등학교 수학에서 공식만 알면 바로 구현이 되지만 이 부분에서는 O(logN)정도 처리를 해야 되기 때문에 어느정도의 아이디어가 필요하다. 그래서 방법이 분할로 처리하는 방법이다. 처리하는 방법은 위에 곱셈 푸는 것을 제대로 이해하면 풀수가 있다. 위에 방식을 그냥 수끼리 곱셈에서 행렬 곱셈으로만 바꾸면 되기 때문이다. 그래서 아래와 같은 식으로 구현하면 된다.

Python

def pow(n):
    if n == 1:
        return A % C
    else:
        result = pow(n // 2)
        if n % 2 == 1:
            return (result * result * A) % C
        else:
            return (result * result) % C

Java

public static long Pow(long base, long expo) {

    if(expo == 1) return base % P;

    long result = FIT(base, expo / 2);

    result = result * result % P;

    if(expo % 2 == 1) return result * base % P;
    else return result;
}

 위 공식처럼 구현하면 천억번 실행할것을 최대 40번 실행해서 처리를 할수있다.

 

정리

1. 행렬 곱셈처리하는 것과 지수 처리하는 함수를 만든다.
2. 지수 처리할때 정수끼리 곱셈을 행렬 곱셈처리하는 하는 함수로 대체한다.
3. 마지막 출력하기전에 %1000연산후에 출력해주라.

Code

Python

  자바처럼 원소 하나씩 출력하지않고  '  '.join(map(lambda x: str(x % 1000)) 람다식을 활용해서 출력하도록 했다. 람다식 처리하는 방식도 같이 공부해두면 나중에 편하다. 

def mul_matrix(expo):
    if expo == 1: return matrix  
    result = mul_matrix(expo // 2)
    if (expo %  2) == 1: return mul(mul(result, result), matrix)
    else: return mul(result, result)

def mul(matrix1, matrix2):
    result = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            for k in range(N):
                result[i][j] += (matrix1[k][j] * matrix2[i][k]) % 1000
    return result
    

N, B = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(N)]
for array in mul_matrix(B):
    print(' '.join(map(lambda x: str(x % 1000), array)))

Java

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

public class Main {
	
	static int N;
	static long B;
	
	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());
		
		int[][] matrix = new int[N][N];
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < N; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		
		int[][] result = matrix_mul(matrix, B);
		
		StringBuilder sb = new StringBuilder();
		
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				sb.append(result[i][j] % 1000).append(" ");
			}
			sb.append("\n");
		}
		
		System.out.println(sb);
		
	}
	
	public static int[][] matrix_mul(int[][] arrays, long expo){
		if (expo == 1) return arrays;
		
		int[][] result = matrix_mul(arrays, expo / 2);
		
		if(expo % 2 == 1) return mul(mul(result, result), arrays);
		else return mul(result, result);
	}
	
	
	public static int[][] mul(int[][] matrix1, int[][] matrix2){
		int[][] result = 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++) {
					result[i][j] += (matrix1[k][j] * matrix2[i][k]) % 1000; 
				}
				result[i][j] = result[i][j] % 1000;
			}
		}
		
		return result;
	}
		
}