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

문제 링크

2740번: 행렬 곱셈

 

www.acmicpc.net

 

---

주의사항

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

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

---

문제 설명

---

접근 방법

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

행렬 곱셈의 원리를 알고 있으면 간단한 반복문으로 해결이 가능한 문제입니다.행렬의 곱셈은 위키백과에 사진을 참고하며 설명하겠습니다.

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

 

ko.wikipedia.org

 

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

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

예를 들면

 

이제 해결 알고리즘을 살펴보면

3중 반복문을 통하여 새로운 배열값에 가로줄과 세로줄의 대응하는 값들을 곱한 값을 더하여 저장하는 것을 반복합니다.

 

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

• arrMul함수에서 if문을 사용하여 B가 1일 때 결과를 반환하도록 하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int arr1[][], arr2[][],arr3[][];	//행렬 값 저장 배열
    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()," ");
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        arr1 = new int[N][M];
        //배열A 저장
        for(int i=0;i<N;i++) {
        	st = new StringTokenizer(br.readLine(), " ");
        	for(int j=0;j<M;j++) {
        		arr1[i][j] = Integer.parseInt(st.nextToken());
        	}
        }
        st = new StringTokenizer(br.readLine()," ");
        M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        arr2 = new int[M][K];
        //배열B 저장
        for(int i=0;i<M;i++) {
        	st = new StringTokenizer(br.readLine(), " ");
        	for(int j=0;j<K;j++) {
        		arr2[i][j] = Integer.parseInt(st.nextToken());
        	}
        }
        arr3 = new int[N][K];
        arrMul(N, M, K);
        //행렬값 BufferedWriter에 저장
        for(int i=0;i<N;i++) {
        	for(int j=0;j<K;j++) {
        		bw.write(arr3[i][j] + " ");
        	}
        	bw.newLine();
        }
        bw.flush();	//결과 출력
        bw.close();
        br.close();
    }
    //배열 곱셈 함수
    public static void arrMul(int N, int M, int K) {
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<K;j++) {
    			for(int k=0;k<M;k++) {
    				arr3[i][j] += arr1[i][k] * arr2[k][j];
    			}
    		}
    	}
    }
}