백준 6604번: Matrix Chain Multiplication

문제

[BOJ][C++] 백준 6604번: Matrix Chain Multiplication

문제는 링크를 클릭해서 볼 수 있다.

풀이

입력 및 저장

행렬의 개수 n을 입력 받고 이어서 n개의 행렬의 정보를 입력 받는다. 행렬의 정보는 행렬의 이름, 행의 개수, 열의 개수로 이루어져있다.

행과 열을 동시에 저장하기 위해 pair<int, int> 자료형을 사용했고, 행렬의 이름으로 행렬의 정보를 접근하기 위해 unordered_map을 사용했다. unordered_map은 key의 hash 값으로 value에 접근할 수 있고 탐색 속도는 O(1)이다.

다음으로 예제 입력이 끝날 때까지 입력을 받기 위해 while (cin >> formula) 를 사용했다.

string formula;

while (cin >> formula) {
	// code
}

행렬 계산

계산식은 문자열로 입력 받는다. for (auto &ch : formula) 로 문자열의 문자에 하나하나씩 접근한다. 문자는 크게 3가지로 나누었다. 열린 괄호 ( , 행렬의 이름 그리고 닫힌 괄호 ).

문제 풀이의 핵심은 행렬의 이름이 나왔을 때 ‘계산해야 할 행렬의 스택’에 행렬을 넣고, 닫힌 괄호 ) 가 나왔을 때 넣었던 행렬을 끄집어내 계산하는 것이다. 열린 괄호 ( 는 행렬 계산에 영향을 미치지 않으므로 무시했다. (입력에서 괄호의 개수가 맞지 않는 등 계산이 아예 불가능한 입력은 주어지지 않는다.)

닫힌 괄호 ) 가 나올 때까지 어떠한 계산도 하지 않는다. 행렬의 이름이 나오면 ‘계산해야 할 행렬의 스택’에 행렬을 계속 넣는다. 그러다 닫힌 괄호를 만나면 뒤에서부터 2개의 행렬을 꺼내어 두 행렬을 계산한다. 이 때 두 행렬이 계산 가능한 지 먼저 확인한다. 위치상 앞의 행렬을 a, 뒤의 행렬을 b라고 하자. a의 column과 b의 row 의 크기가 다르면 행렬 계산을 할 수 없다. 이 경우 false를 반환한다.

계산이 가능하다면 a의 row X b의 row X b의 column로 행렬 계산을 한다. 계산하여 나온 ‘결과 행렬’은 다음 계산을 위해 ‘계산해야 할 행렬의 스택’에 넣는다.

위 과정을 계산식이 끝날 떄까지 반복한다. 모든 계산이 error 없이 끝났다면 true를 반환한다.

예외 케이스로 계산식이 괄호 없이 하나의 행렬만으로 이루어진 경우가 있다. 이 경우 계산이 필요없으므로 for문 시작 전에 true를 반환해준다.

공부

string에서 length()와 size()의 차이

length와 size는 같은 값을 반환하지만 다른 의미를 가지고 있다. length는 문자열의 길이를 반한하고, size는 해당 객체가 사용하는 메모리의 크기를 반환한다. 문자열에서 한 문자의 메모리 크기가 1 바이트이기 떄문에 “abc”라는 문자열이 있을 때, 문자열의 길이도 3, 사용하는 메모리의 크기도 3이 된다.

코드

#include<iostream>
#include<unordered_map>
#include<stack>
using namespace std;

unordered_map<char, pair<int, int>> matrix;     // 입력 받은 행렬들
int count_multiplication = 0;                   // 연산 회수

bool check(string formula) {
    stack<pair<int, int>> matrix_to_calculate;   // 계산해야 할 행렬들의 스택
    pair<int, int> a, b;                         // 계산 중간에 사용할 앞 행렬과 뒤 행렬

    // 연산 횟수 초기화
    count_multiplication = 0;

    // 계산할 행렬이 한 개인 경우 계산 없이 바로 종료한다.
    if (formula.length() == 1)
        return true;

    for (auto &ch : formula) {
        if(ch == '(')
	    continue;
        else if (ch == ')') {
            // 계산할 앞 행렬 a와 뒤 행렬 b를 matrix_to_calculate에서 뺴온다.
            b = matrix_to_calculate.top();
            matrix_to_calculate.pop();
            a = matrix_to_calculate.top();
            matrix_to_calculate.pop();

	    // 행렬 연산이 불가능한 경우 false 반환한다.
	    // a의 column과 b의 row가 다르다.
            if (a.second != b.first)
                return false;

            count_multiplication += a.first * b.first * b.second;

	    // 계산한 행렬을 다음 계산을 위해 matrix_to_calculate에 넣는다.
            matrix_to_calculate.push({a.first, b.second});
        }
        else 
            matrix_to_calculate.push(matrix[ch]);
    }

    // 모든 계산이 error 없이 끝났다.
    return true;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    char name_of_matrix;
    int row, column;

    cin >> n;

    for(int i = 0; i < n; i++) {
        cin >> name_of_matrix >> row >> column;
        matrix[name_of_matrix] = {row, column};
    }

    string formula;

    while(cin >> formula)
        if (check(formula))
            cout << count_multiplication << "\n";
        else
            cout << "error" << '\n';

    return 0;
}

채점 결과