[백준 16637] 괄호 추가하기

분류 

stack, 구현

요구사항

주어진 수식에서 괄호를 추가하여 만들 수 있는 수 중에서 가장 큰 수 찾기

풀이

문제 풀이 흐름은 

1. dfs로 괄호 추가 위치 찾기

2.  괄호 추가 위치 다 찾았을 경우, stack을 이용해 수식 계산하기

 - 괄호가 선택되어졌을때는 stack에서 제일 위에 있는거를 pop하고 연산한 뒤에 다시 넣는다

 - 선택 안되었을 경우, 그냥 stack에 삽입한다.

다른 쉬운 풀이도 있는데 나는 어렵게 푼거 같다

문자열 변환 등등...

 

#include <iostream>
#include <queue>
#include <deque>
#include <string.h>
#include <string>
#include <algorithm>
using namespace std;
string str;
int visit[10];
int n;
int num[10];
string alph[10];
int ans = -987654321;
void dfs(int now) {
	if (now >= n / 2 + 1) {
		deque<string> dq;

		dq.push_back(to_string(num[0]));
		for (int i = 1; i <= (n / 2); i++) {
			if (visit[i] == 0) {
				dq.push_back(alph[i - 1]);
				dq.push_back(to_string(num[i]));
				//	cout<<"push "<< alph[i-1] <<" "<<num[i]<<endl;
			}
			else if (visit[i] == 1) {
				string now = dq.back();
				//	cout<<"pop"<<now<<endl;
				dq.pop_back();
				int nownum = stoi(now);
				int nextnum = num[i];
				int number = 0;
				if (alph[i - 1] == "*") {
					number = nownum*nextnum;
				}
				else if (alph[i - 1] == "+") {
					number = nownum + nextnum;
				}
				else if (alph[i - 1] == "-") {
					number = nownum - nextnum;
				}
				//	cout<<"NUMber"<<number<<endl;
				dq.push_back(to_string(number));
			}
		}
		int tempans = stoi(dq.front());
		dq.pop_front();
		while (!dq.empty()) {
			string now = dq.front();
			//cout<<now<<endl;
			dq.pop_front();
			if (now == "*") {
				tempans *= stoi(dq.front());
				dq.pop_front();
			}
			else if (now == "+") {
				tempans += stoi(dq.front());
				dq.pop_front();
			}
			else if (now == "-") {
				tempans -= stoi(dq.front());
				dq.pop_front();
			}

		}
		ans = max(ans, tempans);
		return;

	}
	//골랐다.
	visit[now] = 1;
	dfs(now + 2);
	//이번꺼 안골랏다
	visit[now] = 0;
	dfs(now + 1);
}
int main() {
	scanf("%d", &n);
	int numcnt = 0;
	int alphacnt = 0;
	for (int i = 0; i < n; i++) {
		if (i % 2 == 0) {
			scanf("%d", &num[numcnt++]);
		}
		if (i % 2 == 1) {
			char ch;
			scanf(" %c", &ch);
			alph[alphacnt++] += ch;
		}
	}
	dfs(1);
	cout << ans << endl;
}