[BaekJoon] 백준 10830번 행렬 제곱

https://www.acmicpc.net/problem/10830

10830번: 행렬 제곱

 

 

 

 

N * N 의 행렬이 주어지면 행렬의 B 제곱을 구하는 문제. 

어떤 숫자를 제곱할 때 아래와 같은 수식으로 나타낼 수 있다.

 

 

재귀함수로 제곱 수/2 로 순환하면서 행렬의 곱셉을 구하면 된다. 

다만 홀수인 경우, 제곱 후에 자신의 값을 다시 곱해주어야 한다. 

 

 

전체 코드 >> 

pow : 제곱

multiply : 행렬 곱셈

 

 * B의 자료형 주의 !(Long)

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

public class Main {
    static int[][] MATRIX;
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
        String[] tmp = br.readLine().split(" ");
        N = Integer.parseInt(tmp[0]);
        long B = Long.parseLong(tmp[1]);
        
        MATRIX = new int[N][N];
        
        for(int i = 0; i<N; i++) {
            String[] t = br.readLine().split(" ");
            
            for(int j = 0; j<N; j++) {
                MATRIX[i][j] = Integer.parseInt(t[j]);
            }
        }
        
        int[][] result = pow(MATRIX, B);
        
        if (B == 1) {
            for(int i = 0; i<N; i++) {
                for(int j = 0; j<N; j++) {
                    result[i][j] %= 1000;
                }
            }
        }
        
        for(int i = 0; i<N; i++) {
            for(int j = 0; j<N; j++) {
                System.out.print(result[i][j]);
                if (j < N-1) {
                    System.out.print(" ");
                }
            }
            System.out.println("");
        }
        
    }
    
    public static int[][] pow(int[][] m, Long n) {
        if (n == 1) {
            return m;
        }
        
        int[][] tmp = pow(m, n/2);
        
        int[][] result = multiply(tmp, tmp);
        
        if (n%2 == 1) {
            result = multiply(result, m);
        }
        
        return result;
    }
    
    public static int[][] multiply(int[][] m1, int[][] m2) {
        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] += m1[i][k] * m2[k][j];
                    result[i][j] %= 1000;
                }
            }
        }
        return result;
    }
}