문제 링크

성능 요약

메모리: 14212 KB, 시간: 104 ms

분류

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

제출 일자

2024년 12월 26일 17:01:18

문제 설명

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

풀이

느낀점

• 행렬의 곱셈을 코드로 쳐본 게 처음이라서 좀 헷갈리고 신기했다.

설계 : 30분(참고)

• 제곱을 분할정복으로 구현하는 방식이다.
• 단, 주어진 제곱수의 최대값이 너무 크기 때문에 dp에 저장하지 않고 단순히 값을 반환하는 재귀함수로 구현한다.
• 요소들을 1000으로 나눈 나머지를 출력해야 하는데, 처음 입력된 수가 1000일 수 있기 때문에 basic 행렬을 입력할때부터 일단 모듈러를 해줘야 예외처리가 가능했다.

코드(Java)

• 구현 시간: 60분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 행렬 제곱_10830
 * Date: 2024.12.26
 */

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
	static int n;
	static int[][] basic;
	static final int MOD = 1000;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

		String[] input = br.readLine().split(" ");
		n = Integer.parseInt(input[0]);
		long b = Long.parseLong(input[1]);

		basic = new int[n][n];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < n; j++) {
				basic[i][j] = Integer.parseInt(st.nextToken()) % MOD;
			}
		}

		int[][] answer = pow(b);

		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				sb.append(answer[i][j]).append(" ");
			}
			sb.append("\n");
		}

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

	private static int[][] pow(long cnt) {
		if (cnt == 1) return basic;

		int[][] half = pow(cnt / 2);
		int[][] mult = matrixMult(half, half);
		if (cnt % 2 == 0) return mult;
		else return matrixMult(mult, basic);
	}

	private static int[][] matrixMult(int[][] a, int[][] b) {

		int[][] result = new int[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				int answer = 0;
				for (int k = 0; k < n; k++) {
					answer += (a[i][k] * b[k][j]) % MOD;
				}
				result[i][j] = answer % MOD;
			}
		}

		return result;
	}
}