취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 6604번 문제인 Matrix Chain Multiplication이다.
문제는 아래 링크를 확인하자.

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

괄호로 주어지는 연산순서는 스택 자료구조를 이용하여 편하게 처리할 수 있다.

N by M 행렬과 P by Q 행렬을 곱할 때, M과 P가 같다면 필요한 곱셈 횟수는 NMQ와 같고 M과 P가 같지 않으면 곱셈을 할 수 없다는 점을 상기해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
#include <stack>
#include <vector>
using namespace std;
typedef long long ll;

ll arr[128][2];

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

	int N; cin >> N;
	while (N--) {
		char c; ll x, y; cin >> c >> x >> y;
		arr[c][0] = x; arr[c][1] = y;
	}

	stack<pair<ll, ll>> stk;

	string s;
	while (cin >> s) {
		ll ans = 0;
		bool chk = 1;
		for (auto c : s) {
			if (c == ')') {
				ll row = stk.top().first;
				ll column = stk.top().second;
				stk.pop();
				if (stk.top().second != row) {
					chk = 0; break;
				}
				ans += stk.top().first * row * column;
				stk.top().second = column;
			}
			else if (c != '(') {
				if (arr[c][0] == 0 && arr[c][1] == 0) {
					chk = 0; break;
				}
				stk.push({ arr[c][0], arr[c][1] });
			}
		}
		if (chk) cout << ans << '\n';
		else cout << "error\n";
	}
}