[백준/Gold IV] 행렬 제곱 - 10830

[Gold IV] 행렬 제곱 - 10830

문제 링크

성능 요약

메모리: 18780 KB, 시간: 204 ms

분류

분할 정복, 분할 정복을 이용한 거듭제곱, 선형대수학, 수학

제출 일자

2024년 12월 19일 17:29:58

문제 설명

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

 

 

 

 

 

---

풀이 및 코드

B번 행렬을 곱해야하는데 B의 범위가 1 ≤ B ≤ 100,000,000,000 임을 유의해야한다.

B가 굉장히 클 수 있으므로 분할 정복으로 문제를 해결해야 한다.

 

+ 80%에서 계속 실패가 떠서 반례를 확인해보았다.

B가 1일 때, 원래의 행렬을 그대로 리턴하도록 코딩되어 있는데

***

2 1

1000 1000

1000 1000

***

위 예시에서 "행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다." 조건을 충족하지 못하므로

행렬의 원소들을 출력할 때 1000으로 나눈 나머지를 출력하도록 수정하였다.

 

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

public class Main {
    private static long[][] origin;
    private static int n;

    private static long[][] multiply(long[][] m1, long[][] m2){ // 행렬 곱
        long[][] res = new long[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for(int k = 0; k < n; k++){
                    res[i][j] = (res[i][j]+m1[i][k] * m2[k][j])% 1000; // 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0
                }
//                res[i][j] %= 1000; // 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0
            }
        }
        return res;
    }

    private static long[][] recursive(long b, long[][] m){ // 분할 정복 방식으로 거듭제곱 구현
        if(b == 1){
            return m;
        }
        long[][] temp = recursive(b/2, m);
        if(b%2 == 0){
            return multiply(temp, temp);
        }else{
            return multiply(multiply(temp, temp), origin);
        }
    }


    private static void print2D(long[][] matrix){ // 행렬 출력
        Arrays.stream(matrix).forEach(i->{
            Arrays.stream(i).forEach(x->System.out.print((x%1000)+" "));
            System.out.println();
        });
    }


    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());
        long b = Long.parseLong(st.nextToken());

        // n*n 행렬 만들기
        origin = new long[n][n];
        for(int i = 0; i < n; i++) {
            origin[i] = Arrays.stream(br.readLine().split(" ")).mapToLong(Long::parseLong).toArray();
        }

        print2D(recursive(b, origin.clone()));

    }
}