백준 10830번 : 행렬 제곱 [자바]

 

 

 

 

✔️ 출처

행렬 제곱 골드 4

 

📖 문제

 

1시간 30분 걸렸다.

생각할게 많았독 옛날에 행렬 연산 했을때도 구현이 잘 안되서 오래걸렸는데

이번에도 마찬가지다..

 

행렬 연산에 대해서 자세히 이해하고 구현해볼 예정이다.

 

설명하기 어렵다.. 

---

🔅 문제 풀이 

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

public class Main {

    static int[][] poweredA; // 제곱된 A 행렬 저장
    static int[][] operand;  // 제곱된 A 행렬을 복사하여 자기 자신을 곱하도록 만들 피연산 행렬
    static int[][][] matrixPowers; // 제곱 연산 결과 행렬
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(st.nextToken());
        long b = Long.parseLong(st.nextToken());

        poweredA = new int[n][n];
        operand = new int[n][n];

        int maxSize = (int)(Math.log(100000000000.0) / Math.log(2)) + 2; // B의 최댓값을 log 연산하여 2의 몇제곱까지인지 사이즈를 얻는다.
        matrixPowers = new int[maxSize][n][n];
        int[][] result = new int[n][n];


        // matrixPowers[1] = A 행렬 초기화
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                matrixPowers[1][i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // matrixPowers[i] = A^(2^(i-1)) 사전 계산
        // 1 = A, 2 = A*A, 3 = A^2 * A^2, 4 = A^4 * A^4...
        for (int i = 1; i < matrixPowers.length; i++) {
            matrixPower(i, n);
        }


        // 가장 높은 비트 위치의 제곱 행렬을 초기 result로 사용
        int highBitPos = (int)(Math.log(Long.highestOneBit(b)) / Math.log(2));
        // ex) b= 4 일때 100 이고 pow = 2, 하지만 dp에 저장된 2번째는 A*A 이므로 우리가 찾는 A^4 는 pow + 1 번째 위치 (A^2 * A^2)
        deepCopyMatrix(matrixPowers[highBitPos + 1], result);


        // 나머지 1비트마다 해당하는 제곱 행렬을 누적 곱
        String bit = Long.toString(b, 2);
        for (int i = 1; i < bit.length(); i++) {
            if (bit.charAt(i) == '1') {
                result = multiplyWithPowerOfA(result, bit.length() - i, n);
            }
        }

        // 출력
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sb.append(result[i][j]).append(" ");
            }
            sb.append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    /**
     * result * matrixPowers[target] 연산 수행
     * result는 지금까지 누적된 결과 행렬, matrixPowers[target]은 A^(2^target)
     */
    private static int[][] multiplyWithPowerOfA(int[][] result, int target, int n) {
        deepCopyMatrix(matrixPowers[target], poweredA);

        int[][] powered = new int[n][n];
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    powered[i][k] = (powered[i][k] + (result[i][j] * poweredA[j][k] % 1000)) % 1000;
                }
            }
        }
        return powered;
    }

    /**
     * matrixPowers[pow] = matrixPowers[pow-1] * matrixPowers[pow-1] 계산 (즉 A^(2^(pow-1)) = A^(2^(pow-2)) * A^(2^(pow-2)))
     */
    private static void matrixPower(int pow, int n) {
        deepCopyMatrix(matrixPowers[pow - 1], poweredA);
        deepCopyMatrix(matrixPowers[pow - 1], operand);

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    matrixPowers[pow][i][k] = (matrixPowers[pow][i][k] + (poweredA[i][j] * operand[j][k] % 1000)) % 1000;
                }
            }
        }
    }

    // 행렬을 깊은 복사
    private static void deepCopyMatrix(int[][] a, int[][] b) {
        for (int i = 0; i < a.length; i++) {
            b[i] = a[i].clone();
        }
    }

}

 

 

 

❗ 오답노트 / 필요한 지식

1.