2740번

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

2740번: 행렬 곱셈

이 문제는 단순한 행렬곱 계산 방식으로 문제를 해결 할 수 있다.

나는 이 문제를 while문을 사용해서 풀었는데, for문으로 하기에는 3중 for문을 써야할 것 같아서 였다.

그래서 while문에 for문을 추가하여 변수2개를 주어 문제를 해결했다.

 

계산 방법은 간단하다 각행과 열을 곱하는 것인데, 예를 들어 3 by 2 행렬과 2 by 3행렬이 있을 때,

행렬 곱은 a11*b11+a12*b21, a11*b12+a12*b22, a11*b13+a12*b23

a21*b11+a22*b21, a21*b12+a22*b22, a21*b13+a22*b23

a31*b11+a32*b21,a31*b12+a32*b22, a31*b13+a32*b23로 나타낼 수 있다.

 

즉, 첫번째 row에 대해 각 column들의 곱의 합을 구하는 것이다.

그럼 만들려고 하는 정답 행렬을 total이라고 했을 때, matrix[row][i]+matrix2[i][column]들의 합을 구한 tmp가 total[row][column]의 값이 되는 것이다.

선형대수를 배웠다면 행렬의 곱은 이해하기 쉬울것이다.

아래의 코드는 행렬의 곱을 이용해서 나타낸 것이다. 하지만 이 문제는 분할 정복을 구현하도록 의도한 문제이다.

package backjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class b2740 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[][] matrix = new int[N][M];
        for(int i=0; i<N; i++){
            st=new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++){
                matrix[i][j]= Integer.parseInt(st.nextToken());
            }
        }//N by M matrix
        st = new StringTokenizer(br.readLine());
        int M1 = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[][] matrix2 = new int[M1][K];
        for(int i=0; i<M1; i++){
            st=new StringTokenizer(br.readLine());
            for(int j=0; j<K; j++){
                matrix2[i][j]= Integer.parseInt(st.nextToken());
            }
        }// M by K matrix
        int[][] total = new int[N][K];
        int row = 0;
        int column=0;
        while (row<N){
            int tmp=0;
            for(int i=0; i<M; i++) {
                tmp += matrix[row][i] * matrix2[i][column];
            }
            total[row][column]=tmp;
            column++;
            if(column==K){
                row++;
                column=0;
            }
        }//matrix multiple
        StringBuilder sb = new StringBuilder();
        for(int[] i: total){
            for(int j : i){
                sb.append(j).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
}

그래서 분할 정복으로 푸는 방법을 찾아 보던 중에 스트라센 알고리즘을 알았다.

스트라센 알고리즘에 관한 내용은 아래의 블로그 작성자 분께서 엄청 잘 설명하셔서 이 글을 보면 이해가 잘 될 것이라고 생각한다.

 

https://st-lab.tistory.com/245

[백준] 2740번 : 행렬 곱셈 - JAVA [자바]