백준 10830번 행렬 제곱JAVA 구현해보기

---

```

백준 10830번 행렬 제곱 JAVA 구현해보기

```

이번 글을 통해 배워갈 내용

1.  백준 10830번 풀이

---

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

10830번: 행렬 제곱

 

 

 

백준 10830번 행렬 제곱은

난이도 골드 등급의 문제로서

 

N * N 크기의 행렬 A 가 주어지고 A의 B 제곱을 구하면 됩니다.

N 은 2 이상 5 이하이고

B는 1 이상 100,000,000,000 이하입니다.

 

각 원소의 값이 커질 수 있으니 1000으로 나눈 나머지를 출력해줍니다.

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

행렬이나 행렬곱에 대해 정보가 필요하신 분은

아래 위키를 참조해주세요~
https://ko.wikipedia.org/wiki/%ED%96%89%EB%A0%AC_%EA%B3%B1%EC%85%88

행렬 곱셈 - 위키백과, 우리 모두의 백과사전

 

행렬을 입력받고

행렬을 곱하는 건

원리만 알면 간단하지만

 

100,000,000,000 제곱을 계속 곱해주는 게 아니고

뭔가 다른 방법으로 찾는 생각을 하는 게 시간이 조금 걸렸네요

 

방법은 의외로 간단합니다.

제곱이 짝수번 일 경우

연산된 값을 그대로 재활용해주면 됩니다.

예) A ^ 4 = (A^2) * (A^2)

그렇게 되면 연산 횟수가 Log(n) 2로 줄어듭니다.

 

속도는 생각보다 빠르게 나왔지만

추후에는 고윳값이 있는 행렬의 경우

A = PD(P^-1)

A^N = P(D^N)(P^-1)

을 이용하거나

조르단 방법을 이용해 보는 것도 괜찮겠다는 생각이 들었습니다.

 

전체 코드는 아래와 같습니다.

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

public class Main {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    // 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.
    static final int MATRIX_MOD = 1000;

    public static void main(String[] args) throws IOException {
        // 행렬의 크기, 제곱의 횟수를 입력을 받는다
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        final int arraySize = Integer.parseInt(st.nextToken());
        final long powerSize = Long.parseLong(st.nextToken());

        // 행렬을 입력받는다
        int[][] inputMatrix = findInputMatrix(arraySize);
        // 행렬의 제곱을 구한다
        int[][] sol = powerMatrix(inputMatrix, arraySize, powerSize);
        // 결과를 출력한다
        printMatrix(sol, arraySize);
    }

    // 행렬을 입력받는다
    private static int[][] findInputMatrix(int arraySize) throws IOException {
        int[][] matrix = new int[arraySize][arraySize];
        for (int i = 0; i < arraySize; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < arraySize; j++) {
                matrix[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        return matrix;
    }

    // 행렬의 제곱을 구한다
    private static int[][] powerMatrix(int[][] inputMatrix, int arraySize, long powerSize) {
        int[][] tempMatrix = inputMatrix;
        int[][] retMatrix = initIMatrix(arraySize);
        while (powerSize > 0) {
            if (powerSize % 2 == 1) {
                retMatrix = multiplyMatrix(tempMatrix, retMatrix, arraySize);
            }
            tempMatrix = multiplyMatrix(tempMatrix, tempMatrix, arraySize);
            powerSize /= 2;
        }
        return retMatrix;
    }

    // I 행렬을 구한다 (대각이 1 나머지 값들은 0인 행렬)
    private static int[][] initIMatrix(int arraySize) {
        int[][] retMatrix = new int[arraySize][arraySize];
        for (int i = 0; i < arraySize; i++) {
            for (int j = 0; j < arraySize; j++) {
                if (i == j) {
                    retMatrix[i][j] = 1;
                } else {
                    retMatrix[i][j] = 0;
                }
            }
        }
        return retMatrix;
    }

    // 두 행렬의 곱을 구한다
    private static int[][] multiplyMatrix(int[][] lhsMatrix, int[][] rhsMatrix, int arraySize) {
        int[][] retMatrix = new int[arraySize][arraySize];
        for (int i = 0; i < arraySize; i++) {
            for (int j = 0; j < arraySize; j++) {
                retMatrix[i][j] = 0;
                for (int k = 0; k < arraySize; k++) {
                    retMatrix[i][j] += (lhsMatrix[i][k] * rhsMatrix[k][j]);
                }
                retMatrix[i][j] %= MATRIX_MOD;
            }
        }
        return retMatrix;
    }

    // 결과값을 출력한다.
    private static void printMatrix(int[][] matrix, int arraySize) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < arraySize; i++) {
            for (int j = 0; j < arraySize; j++) {
                sb.append(matrix[i][j]).append(' ');
            }
            sb.setLength(sb.length() - 1);
            sb.append("\n");
        }
        sb.setLength(sb.length() - 1);
        System.out.print(sb);
    }
}

//codemasterkimc.tistory.com [김씨의 코딩 스토리]

 

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩 하시길 바랍니다 ~ :)

 

---