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

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

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

 

숫자들 사이에 연산자를 끼워넣고 중위순회 형식으로 이루어진 연산 식의 결과값의 최대, 최소값을 구하는 문제다.

사칙연산의 연산자 우선순위를 신경써야하는데, 연산자 우선순위를 신경써서 후위표기식으로 변환해준 후 연산을 수행했다.

 

문제 해결 방법은 아래와 같다.

 

1. 우선 백트래킹 기법으로 주어진 연산자 개수로 나올 수 있는 모든 경우의 수를 구한다.

2. 각각의 경우의 수에 대하여 후위표기법으로 사칙연산을 수행하고 최대, 최소값을 비교한다.

 

#include <iostream>
#include <stack>

#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
using namespace std;

int n;
int num[11];
int oper[11];
int oper_cnt[4];
bool priority[] = { 0, 0, 1, 1 };
int max_val = -1e9, min_val = 1e9;

void calculate() {
	int idx = 0, prev, cur;
	int a, b;

	// 후위표기식으로 계산하기
	// 숫자를 저장하기 위한 스택과 연산자를 저장하기 위한 스택, 두 개의 스택을 사용
	stack<int> st;
	stack<int> op;

	while (idx < n) {
		// 숫자는 그냥 넣어줌
		st.push(num[idx]);
		// 연산자는 숫자의 수보다 하나 더 적지만 마지막 값으로 
		// 연산자 우선순위가 낮은 0값을 주어서 연산자 스택을 모두 비울 수 있도록 함
		cur = oper[idx];

		// 연산자 스택의 가장 위에 있는 값이 현재 연산자의 우선순위보다 같거나 높은 경우 연산 수행
		while (!op.empty() && priority[op.top()] >= priority[cur]) {
			prev = op.top();
			// 연산 스택에서 값 두개를 꺼낸 뒤 계산 후 결과값을 다시 넣어줌
			b = st.top(), st.pop();
			a = st.top(), st.pop();
			if (prev == 0) st.push(a + b);
			else if (prev == 1) st.push(a - b);
			else if (prev == 2) st.push(a * b);
			else st.push(a / b);

			op.pop();
		}
		// 현재 연산자 연산자 스택에 집어넣음
		op.push(cur);
		++idx;
	}

	int res = st.top();
	min_val = min(min_val, res);
	max_val = max(max_val, res);
}

void dfs(int len) {
	// 연산자를 모두 채우고 나서 연산 수행
	if (len >= n - 1) {
		calculate();
		return;
	}

	// 백트래킹으로 연산자 순열을 구함
	for (int i = 0; i < 4; i++) {
		if (!oper_cnt[i]) continue;
		oper[len] = i;
		--oper_cnt[i];
		dfs(len + 1);
		++oper_cnt[i];
	}
}

void solution() {
	cin >> n;
	for (int i = 0; i < n; i++) cin >> num[i];
	for (int i = 0; i < 4; i++) cin >> oper_cnt[i];

	dfs(0);
	cout << max_val << '\n' << min_val;
}

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

	return 0;
}

메모리: 2024 kb

시간: 8 ms