백준 10830 행렬제곱

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

행렬제곱문제

분할정복의 기초를 다지기에 진짜좋은문제인거같다..ㅎㅎ;;

다른 골드5 문제들은 분할정복 도되지만 다른 풀이가더 매끄러운? 문제들이많아서

해당문제를 풀었다.

골드3 골드2까지 풀고 얼른 넘어가도록 하자

메인로직

1. 2로 나눳을때 나머지가 1인지 0인지 체크
   ex. 5=> 2 2+ 1 // 4 => 2 2
2. 1번의 로직을 1이 될떄까지 재귀를 타줌 => 1이 될떄는 원래 행렬반환
3. 그럼 사실상 2 또는 3이 될떄가지 재귀가 되는데 그때부터 행렬연산을 통해 return 해줌
4. 연산할때 %1000 해주고 출력할때 %1000 해주기

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

public class 행렬제곱 {
	static int[][] array;
	static int N;
	static long B;

	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		B = Long.parseLong(st.nextToken());
		array = new int[N][N];
		
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<N;j++) {
				array[i][j] = Integer.parseInt(st.nextToken())%1000;
			}
		}
		
		int[][] answer = div(B);
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				sb.append(answer[i][j]%1000).append(" ");
			}
			sb.append("\n");
		}
		System.out.println(sb);
	}
	public static int[][] div(long count){
		if(count==1) {
			return array;
		}
		int[][] canswer = new int[N][N];
		int[][] fanswer = div(count/2);
		if(count%2==1) {
			canswer = cal(fanswer,fanswer);
			canswer = cal(canswer,array);
		}
		else {
			canswer = cal(fanswer,fanswer);
		}
		return canswer;
		
	}

	public static int[][] cal(int[][] a,int[][]b){
		int[][] canswer = new int[N][N];
		
		/*
		1 2  1 2           (0,0)1*1(0,0) +(0,1)2*3(1,0)
		3 4  3 4 
		*/
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				int sum = 0;
				
				for(int k=0;k<N;k++) {
					sum += a[i][k]*b[k][j];
				}
				canswer[i][j] = sum%1000;
			}
		}
		
		
		return canswer;
		
	}

}

long 처리와.. ㅎㅎ;; 재귀를 잘못설정 .. 그리고 많은 배열선언으로 인해 시행착오가있었다 ㅎㅎ;;

얼른 2 3으로넘어가자