행렬 제곱

문제

문제 설명

크기가 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제곱한 결과를 출력한다.

입출력 예

입력	출력
2 5
1 2	69 558
3 4	337 406
3 3
1 2 3	468 576 684
4 5 6	62 305 548
7 8 9	656 34 412
5 10
1 0 0 0 1	512 0 0 0 512
1 0 0 0 1	512 0 0 0 512
1 0 0 0 1	512 0 0 0 512
1 0 0 0 1	512 0 0 0 512
1 0 0 0 1	512 0 0 0 512

입출력 예 설명

아이디어

제출 코드

import java.io.*;
import java.util.StringTokenizer;

public class four10830 {
    private static BufferedReader reader;
    private static StringTokenizer infoToken;
    private static int n;
    private static long b;
    private static int[][] arr;
    private static int[][] result;
    private static int[][] temp;
    private static StringBuilder builder;
    private static BufferedWriter writer;
    public void solution() throws IOException {
        reader = new BufferedReader(new InputStreamReader(System.in));
        writer = new BufferedWriter(new OutputStreamWriter(System.out));
        builder = new StringBuilder();
        infoToken = new StringTokenizer(reader.readLine());
        n = Integer.parseInt(infoToken.nextToken());
        b = Long.parseLong(infoToken.nextToken());
        arr = new int[n][n];
        result = new int[n][n];
        temp = new int[n][n];
        for (int i = 0; i < n; i++) {
            infoToken = new StringTokenizer(reader.readLine());
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(infoToken.nextToken()) % 1000;
                result[i][j] = arr[i][j];
            }
        }
        matrixMul(1L);
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                builder.append(result[i][j]).append(" ");
            }
            builder.append('\n');
        }
        writer.write(builder.toString());
        writer.flush();
    }

    private void matrixMul(long depth) {
        if (depth == b) return;
        for (int i = 0; i < n; i++) {
            temp[i] = result[i].clone();
        }
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < n; col++) {
                int val = 0;
                for (int i = 0; i < n; i++) {
                    val += (temp[row][i] * arr[i][col]) % 1000;
                }
                result[row][col] = val % 1000;
            }
        }
        matrixMul(depth + 1);
    }

    public static void main(String[] args) throws IOException {
        new four10830().solution();
    }
}

중간에 깊은 복사가 있어서 자꾸 메모리 초과가 뜬다

→ 깊이를 반띵해서 계속 재귀 호출

모범 풀이

import java.io.*;
import java.util.StringTokenizer;

public class four10830 {
    private static BufferedReader reader;
    private static StringTokenizer infoToken;
    private static int n;
    private static long b;
    private static int[][] arr;
    private static int[][] result;
    private static int[][] temp;
    private static StringBuilder builder;
    private static BufferedWriter writer;
    public void solution() throws IOException {
        reader = new BufferedReader(new InputStreamReader(System.in));
        writer = new BufferedWriter(new OutputStreamWriter(System.out));
        builder = new StringBuilder();
        infoToken = new StringTokenizer(reader.readLine());
        n = Integer.parseInt(infoToken.nextToken());
        b = Long.parseLong(infoToken.nextToken());
        arr = new int[n][n];
        result = new int[n][n];
        temp = new int[n][n];
        for (int i = 0; i < n; i++) {
            infoToken = new StringTokenizer(reader.readLine());
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(infoToken.nextToken()) % 1000;
                result[i][j] = arr[i][j];
            }
        }
        result = pow(arr, b);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                builder.append(result[i][j]).append(" ");
            }
            builder.append('\n');
        }
        writer.write(builder.toString());
        writer.flush();
    }

    private int[][] pow(int[][] arr, long depth) {
        if (depth == 1L) return arr;

        int[][] ret = pow(arr, depth / 2);
        ret = multiply(ret, ret);
        if (depth % 2 == 1L) {
            ret = multiply(ret, arr);
        }
        return ret;
    }

    private int[][] multiply(int[][] arrOne, int[][] arrTwo) {
        int[][] temp = new int[n][n];
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < n; col++) {
                for (int i = 0; i < n; i++) {
                    temp[row][col] += (arrOne[row][i] * arrTwo[i][col]);
                    temp[row][col] %= 1000;
                }
            }
        }
        return temp;
    }

    public static void main(String[] args) throws IOException {
        new four10830().solution();
    }
}