[삼성 14888] 연산자 끼워넣기

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

문제 설명

1. N개의 순열
2. N-1개의 연산자를 N개 순열 사이에 끼워넣었을 때 계산의 결과의 최댓값과 최솟값을 찾아라
3. 연산자는 +,-,*,/ 순으로 몇개씩 있는지가 주어진다.
4. 계산할 땐 우선순위 없이 앞에서부터 차례대로한다.
5. 음수/양수 계산 시엔 양의 몫을 구해 음수화해준다.(나누는 수는 항상 양수이다.)

아이디어

N<11이므로 완전탐색이 가능하다고 생각했고, 재귀함수에서 현재까지 계산한 값을 받아서 4개의 연산자를 한번씩 덧붙여서 재귀하면 된다.
참고로 결과물(중간결과물 포함)이 다 10만(10^9)이하래서 int로 해결가능하다.

삽질

1. 구현이 오래걸림^^... 처음에 연산자 4개 FOR문 돌려서 겹치는 과정 일반화 해줬는데(중간과정은 좀 다르게)
   그게 마음에 안들어서 for없애고 걍 줄줄썼다가 다시 돌아옴^^^..
2. 나눗셈 구현에서 음수/양수, 양수/양수 케이스를 반대로 구현해갖고 어디서 틀렸는지 몰라서 traker란 vector에다 결과물이 만들어준 연산자 순서를 저장해서 결과물이 나올 때 찍어봤다.

코드

https://www.acmicpc.net/source/23167877

#include<iostream>
#include<math.h>
#include<vector>
using namespace std;
vector<int> nums;
int mmin=pow(10,9), mmax=-pow(10,9);//전체 결과중에서
int counter = 0;
void one_proc(int mom_res, int s, vector<int> yeons,vector<int> tracker) {//s는 연산자가 적용될 인덱스
	counter++;

	if (s == nums.size()) {
		/*
		cout << "계산결과 비교중" << mmin << " , " << mmax << " , " << mom_res << endl;
		for (int i = 0; i < tracker.size(); i++) {
			cout << tracker[i] << " ";
		}
		cout << endl;
		*/
		mmin = min(mmin, mom_res);
		mmax = max(mmax, mom_res);
		return;
	}
	for (int i = 0; i < 4; i++) {
		int res = mom_res;
		if (yeons[i] <= 0) {
			continue;
		}
		yeons[i]--;
		
		if (i == 0) {
			res = res + nums[s];
		}
		else if (i == 1) {
			res = res - nums[s];
		}
		else if (i == 2) {
			res = res * nums[s];
		}
		else if (i == 3) {
			if (res > 0) {
				res = res / nums[s];
			}
			else {
				res = -(abs(res) / nums[s]);
			}
		}
		vector<int> temp_tracker = tracker;
		temp_tracker.push_back(i);
		/*
		cout << "right before dfs" << endl;
		for (int i = 0; i < temp_tracker.size(); i++) {
			cout << temp_tracker[i] << " ";
		}
		cout << " == " << res << endl;
		*/
		one_proc(res, s + 1, yeons,temp_tracker);
		yeons[i]++;//복구
	}
}


int main() {
	int n;
	vector<int> yeons;//4가지 연산자의 개수

	cin >> n;
	int num;
	for (int i = 0; i < n; i++) {
		cin >> num;
		nums.push_back(num);
	}
	for (int i = 0; i < 4; i++) {
		cin >> num;
		yeons.push_back(num);
	}
	vector<int> tracker;
	one_proc(nums[0], 1, yeons,tracker);
	cout << mmax << endl;
	cout << mmin << endl;
}