대엉코딩

www.acmicpc.net/problem/15659

1. 풀이방법

- 일단 숫자는 고정이고, 연산자만으로 모든 순열을 다 짜고 연산을 시작한다.

- 문제는 연산자 우선순위에 따른 계산을 해야한다는 것인데

- 저 같은경우 * 또는 / 먼저 연산을 완료한 후 새로운 벡터에 넣어놓고 그 후 + 또는 - 연산을 해주었습니다.

- 이과정에서 구현이 매우 까다로웠는데,

- 먼저 해야하는 것은 * 또는 / 가 나오는 경우 이 연산자들이 연속되어있는 곳 까지는 연산을 계속해줍니다.

(예를 들어 5+7*4*3-3) 이런 경우 *가 처음 등장하면 뒤쪽에 -가 나오기 전까지는 쭉 연결해서 연산을 해줍니다.

- 그후 덧셈, 뺄셈 연산을 수행하는데, 예외사항들이 많아 너무 복잡한 문제였습니다. 개인적으로......

- 저 말고는 제 코드를 이해하는 분이 계실지가..ㅋㅋㅋㅋ

2. 주의사항

- 테스트케이스를 보면서 수정해나가면서 짠 후 ,, 90퍼에서 계속 실패가 떠서 예외사항을 직접 찾아 해매야 했습니다.

3. 나의코드

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

int N,tmp;
vector<long long> numarr;
vector<long long> oper;
vector<long long> tmpoper;
long long maxresult = -9999999999;
long long minresult = 9999999999;
bool allplusorminus;

void inputs() {
	cin >> N;
	for (int i = 0; i < N; i++) { cin >> tmp; numarr.push_back(tmp); }
	for (int i = 0; i < 4; i++) { cin >> tmp; oper.push_back(tmp); }
}

int makenum() {
	vector<long long> tmparr;
	int index = 0;
	for (int i = 0; i < tmpoper.size(); i++) { //곱셈 나눗셈 먼저
		if (tmpoper[i] == 2 || tmpoper[i] == 3) {
			int tempint=numarr[index];
			while (1) { //연속되는 곱셈,나눗셈까지는 모두 같이 처리
				if (i == tmpoper.size() || tmpoper[i] == 0 || tmpoper[i] == 1) { index++; break; }
				if (tmpoper[i] == 2) { //곱셈
					tempint *= numarr[index + 1];
					index++;
				}
				else { //나눗셈
					tempint /= numarr[index + 1];
					index++;
				}
				i++;
			}
			tmparr.push_back(tempint);
			i--;
		}
		else { //아래와 같이 생각해줘야할 예외사항이 너무 많다.!!!!!!!!!!!!!!!
			if (i==0 || i == tmpoper.size() - 1){ 
				tmparr.push_back(numarr[index]); index++;
				if (tmpoper.size() == 1) tmparr.push_back(numarr[index]);
			}
			if (i < tmpoper.size() - 1 && (tmpoper[i + 1] == 0 || tmpoper[i + 1] == 1)) { 
				tmparr.push_back(numarr[index]);
				index++;
			}
		}
	}
	long long result=tmparr[0];
	index = 1;
	for (int i = 0; i < tmpoper.size(); i++) {
		if (tmpoper[i] == 0 || tmpoper[i] == 1) {
			if (tmpoper[i] == 0) { // 덧셈
				result += tmparr[index];
				index++;
			}
			else { //뺄셈
				result -= tmparr[index];
				index++;
			}
		}
	}
	return result;
}

void makecase(int cnt) {
	if (cnt == N - 1) {
		/*cout << numarr[0];
		for (int i = 0; i < tmpoper.size(); i++) {
			if (tmpoper[i] == 0) { cout << " + "; }
			if (tmpoper[i] == 1) { cout << " - "; }
			if (tmpoper[i] == 2) { cout << " * "; }
			if (tmpoper[i] == 3) { cout << " / "; }
			cout << numarr[i + 1];
		}
		cout << "\n";*/
		if (makenum() > maxresult) { maxresult = makenum(); }
		if (makenum() < minresult) { minresult = makenum(); }
		return;
	}
	for (int i = 0; i < 4; i++) {
		if (oper[i] != 0) {
			tmpoper.push_back(i);
			oper[i]--;
			makecase(cnt + 1);
			oper[i]++;
			tmpoper.pop_back();
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	makecase(0);
	cout << maxresult << "\n" << minresult << "\n";
	return 0;
}