백준 6604번: Matrix Chain Multiplication

 

풀이

  예제를 보면 알겠지만 N개의 행렬이 주어지고, N개의 행렬곱셈식이 잇달아 주어진다. 각 행렬곱셈식마다 몇번의 연산이 수행되는지 출력하면 되는 문제이다. () 안의 식을 먼저 연산해야 하기 때문에 자료구조 중에서 스택을 사용하였다.

 

 입력으로 '(' 이 들어오면 무시하고, 알파벳만 스택에 push하도록 한다. 그러다 ')'을 만나면 스택에서 두 개의 알파벳을 꺼내 곱하면 된다.

 

행렬이 이름(A, B, C, ...) , x, y라는 3개의 특징을 갖고 있기 때문에 matrix라는 구조체를 만들어주었고, 알파벳으로 검색하기 쉽도록 map에 저장하였다.

 

 

코드

#include <iostream>
#include <stack>
#include <map>

using namespace std;

typedef struct matrix {
	int x;
	int y;
};

void init() {
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(false);
}

int n;
map<char, matrix> matrixs;
stack<matrix> s;

int main() {
	init();

	cin >> n;
	for (int i = 0; i < n; i++) {
		char name;
		matrix m;
		cin >> name >> m.x >> m.y;
		matrixs[name] = m;
	}

	string input;
	while (cin >> input) {
		matrix m1, m2;
		int sum = 0;


		for (int i = 0; i < input.length(); i++) {
			if (input.length() == 1) break;

			if (input.at(i) == '(') continue;
			else if (input.at(i) == ')') {
				m1 = s.top(); s.pop();
				m2 = s.top(); s.pop();

				if (m1.x != m2.y) {
					sum = -1;
					break;
				}

				matrix m3;
				m3.x = m2.x; m3.y = m1.y;
				sum += (m1.x * m1.y * m2.x);
				s.push(m3);
			}
			else {
				s.push(matrixs[input.at(i)]);
			}
		}

		if (sum == -1) cout << "error\n";
		else cout << sum << "\n";
	}
}