[Baekjoon, C++] 2740번: 행렬 곱셈

도입

백준 단계별 풀기에서 분할정복 여섯 번째 문제이다.

링크는 아래와 같다.

www.acmicpc.net/problem/2740

2740번: 행렬 곱셈

---

백준 2740번 문제, 입력, 출력

---

백준 2740번 입출력 예제 1

---

풀이

1. 행렬을 어떻게 받을 것인가, 2차원 배열로 받겠다. 행과 열을 표현할 수 있기 때문이다. 

 

2. 곱셈을 어떻게 할 것인가! 행렬의 곱셈을 다들 배웠다고 가정을 하겠다. 다음 그림 처럼 곱셈 로직을 짜겠다! 예를 들어서 2x3 크기의 행렬과 3x2 행렬을 곱셈하면 2x2행렬이 결과로 출력된다. Why? 첫 번째 행렬의 행과 두 번째 행렬의 열을 결과로 가진다고 생각하면 된다. 따라서 2x2이다. 그렇다면, 우리가 NxM 과 MxK를 곱한다면 NxK의 행렬이 나온다. 여기서 N은 i, K은 j이다. 따라서 for문 밖으로 i,j를 두고 M(=k)의 연산을 제일 안에 넣어준다.

행렬의 곱셈 로직

 

---

코드

 

#include<iostream>

#define MAX 100

using namespace std;

int matrixA[MAX][MAX], matrixB[MAX][MAX];
int result[MAX][MAX];

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, M, K;

    cin >> N >> M;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            cin >> matrixA[i][j];

    cin >> M >> K;
    for (int i = 0; i < M; i++)
        for (int j = 0; j < K; j++)
            cin >> matrixB[i][j];

    for (int i = 0; i < N; i++)
        for (int j = 0; j < K; j++)
            for (int k = 0; k < M; k++)
                result[i][j] += (matrixA[i][k] * matrixB[k][j]);

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < K; j++)
            cout << result[i][j] << " ";
        cout << "\n";
    }

    return 0;
}

 

---

마무리

풀면서, 이것을 분할 정복 문제인가? 했다. 아마 다음 문제의 행렬 제곱을 위한 행렬 맛보기이지 않을까?! 

 

자아~ 다음 문제로 가보자ㅎㅎ