[백준] 단계별로 풀어보기(단계:20,분할 정복,JAVA)10830번, 행렬 제곱

문제 링크

10830번: 행렬 제곱

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

분할 정복 알고리즘은 일정한 간격으로 입력된 값을 분할하여 조건에 맞는지 확인하고 틀리면 다시 일정한 간격으로 분할하는 것을 반복하여 조건에 만족할 때까지 진행하는 알고리즘입니다.

행렬 곱셈의 원리와 제곱의 곱셈을 분할 정복하는 방법만 알면 풀 수 있는 문제입니다. 행렬의 곱셈은 위키백과에 사진을 참고하며 설명하겠습니다.

행렬 곱셈 - 위키백과, 우리 모두의 백과사전

 

 

 

 

N × M의 배열과 M × K의 배열을 곱하면 N × K 크기의 배열이 만들어집니다.

N × K 배열의 값은 가로줄과 세로줄의 대응하는 값들의 곱을 모두 더한 값이 됩니다.

예를 들면

 

이제 제곱의 곱셈을 분할 정복으로 표현하면 (행렬 = A)

A⁴ = (A²)² = ((A)²)²

위와 같은 형태로 계수가 1이 될 때까지 줄인 이후 제곱으로 분할 정복을 재귀를 통해 진행하여 결과를 구하는 것입니다. A는 행렬이기 때문에 행렬에 맞는 곱셈 알고리즘을 사용하여 분할 정복을 이루면 행렬 제곱에 대한 결과를 얻을 수 있습니다.

 

문제에 대한 해결 알고리즘은(행렬 = A)1. 제곱 형태로 만들기 위해 제곱수/2를 합니다.2. 제곱수가 홀수이면 Aⁿ*A에 형태에서 (Aⁿ)² * A의 형태로 만들어갑니다.3. 제곱수가 짝수이면 Aⁿ에 형태에서 (Aⁿ)²으로 만들어갑니다.4. 제곱수가 1이면 A 자체를 반환합니다.5. 재귀를 반복하면서 행렬에 제곱을 분할하였다가 합치는 것을 반복하여 행렬 제곱의 값을 구합니다.

 

※이 문제에서는 제곱수가 매우 큰 수가 들어갈 수 있음으로 배열에 저장부터 1000으로 나누어 나머지를 구하였습니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 사용하여 띄어쓰기 기준으로 N,B와 행렬값을 저장하였습니다.
• 행렬 제곱/행렬 곱셈을 구하는 arrPow/arrMul함수를 만들었습니다.
• 함수를 실행 후 BufferedWriter에 for문을 통해 배열에 값을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• arrPow함수에서 재귀를 통하여 제곱의 형태로 만들었습니다.
• arrMul함수에서 행렬에 곱셈에 대한 공식을 알고리즘으로 3중 for문을 이용하여 만들었습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int N;	//행렬 크기
	static int MOD = 1000;	//나머지 구할 때 나누는 값
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //-----입력값 저장 및 배열 초기화---------
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        long B = Long.valueOf(st.nextToken());
        int[][] arr = new int[N][N];
        for(int i=0;i<N;i++) {
        	st = new StringTokenizer(br.readLine(), " ");
        	for(int j=0;j<N;j++) {
        		arr[i][j] = Integer.parseInt(st.nextToken()) % MOD;
        	}
        }
        int[][] result = arrPow(arr, B);	//함수 실행
        //결과 BufferedWriter 저장
        for(int i=0;i<N;i++) {
        	for(int j=0;j<N;j++) {
        		bw.write(result[i][j] + " ");
        	}
        	bw.newLine();
        }
        bw.flush();	//결과 출력
        bw.close();
        br.close();
    }
    //-------행렬 제곱 함수---------
    public static int[][] arrPow(int[][] A, long size) {
    	if(size==1)
    		return A;
    	
    	int[][] temp = arrPow(A, size/2);
    	
    	if(size%2==0) {
    		return arrMul(temp,temp);
    	}else {
    		return arrMul(arrMul(temp, temp), A);
    	}
    }
    //--------행렬 곱셈 함수-----------
    public static int[][] arrMul(int[][] A, int[][] B){
    	int[][] temp = new int[N][N];
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<N;j++) {
    			for(int k=0;k<N;k++) {
    				temp[i][j] += A[i][k] * B[k][j];
    				temp[i][j] %= MOD;
    			}
    		}
    	}
    	return temp;
    	
    }
}