[ boj : 15659 ] 연산자 끼워넣기(3)

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

15659번: 연산자 끼워넣기 (3)

먼저 이 밑에 두 문제를 안푸신 상태라면 풀고 오시는 걸 추천드립니다.

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

14888번: 연산자 끼워넣기

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

15658번: 연산자 끼워넣기 (2)

해설 : 연산자 끼워넣기 1번과 2번하고는 달리 3번에서는 '우선순위'라는 까다로운 조건이 추가된 상태입니다.

 

문제를 해결하기 전에 우린 어떻게 연산자의 '우선순위'를 정의하고 풀어 나갈 수 있을까요??

지금부터 이야기하는 부분은 만약 이해가 잘 안가신다면 그냥 머릿속에 암기식으로 박아버리는 걸 추천드립니다. 이유는 이해안가서 여기에 시간 쏟는 것보단 그냥 공식처럼 생각하시는 것이 더 좋은 방법이 될 수도 있더라구요.

 

https://boomrabbit.tistory.com/168

[ boj : 1918 ] 후위 표기식

이 문제에서 사용되는 설명과 동일합니다.

 

'x,/' 가 '+,-' 보다 우선순위가 높으므로, 먼저 계산을 해주어야 합니다. 그럴려면 'x,/'가 '+,-' 를 만났을때는 아무동작을 하면 안되겠죠. 반대로 '+,-' 가 'x,/'를 만났다면?? 그제서야 'x,/' 연산을 실행해 주는 것 입니다. 

그러면 결국 'x,/'가 먼저 계산이 되겠죠.

 

이를 우린 스택 2개를 사용할 것 입니다.

하나는 연산자만 담는 스택, 나머지 하나는 수만 담는 스택

 

이때, 연산자의 개수는 수의 개수보다 1개가 적으니 이를 유의하셔야겠죠?

 

로직은 이렇습니다.

#include<bits/stdc++.h>

using namespace std;

int n;
int arr[11],op[4],cb[11];
int Max = -(int)1e9, Min = (int)1e9;

void solve();
void dfs(int depth);
int get_num();
int calc(int x, int y, int o);

int main()
{
	int t = 1;
	while (t--)
		solve();
	return 0;
}
void solve()
{
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	for (int i = 0; i < 4; i++)
		cin >> op[i];

	dfs(0);
	cout << Max << "\n" << Min;
}
void dfs(int depth)
{
	if (depth == n-1) {
		Max = max(Max, get_num());
		Min = min(Min, get_num());
		return;
	}

	for (int i = 0; i < 4; i++) {
		if (op[i]) {
			op[i]--;
			cb[depth] = i;
			dfs(depth + 1);
			cb[depth] = 0;
			op[i]++;
		}
	}
}
int get_num()
{
	int priority[4] = { 0,0,1,1 };

	stack<int> s1, s2;
	for (int i = 0; i < n; i++)
	{
		s1.push(arr[i]);
		if (i < n - 1)
		{
			if (s2.empty())s2.push(cb[i]);
			else {
				while (!s2.empty() && priority[s2.top()] >= priority[cb[i]]) {
					int x = s1.top(); s1.pop();
					int y = s1.top(); s1.pop();
					int ret = calc(y, x, s2.top());
					s2.pop();
					s1.push(ret);
				}
				s2.push(cb[i]);
			}
		}
	}
	while (!s2.empty())
	{
		int x = s1.top(); s1.pop();
		int y = s1.top(); s1.pop();
		s1.push(calc(y, x, s2.top()));
		s2.pop();
	}
	return s1.top();
}
int calc(int x, int y, int o)
{
	switch (o)
	{
	case 0:
			return x + y;
	case 1:
			return x - y;
	case 2:
			return x * y;
	case 3:
			return x / y;
	}
}