[C++][백준] - 연산자 끼워넣기 (14888번)

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

14888번: 연산자 끼워넣기

🔔 문제 : 

(2<= N <=11) N개의 수로 이루어진 수열이 주어집니다.

 

이때 사칙연산인 + - * / 의 갯수도 총합 N-1개 주어집니다.

 

이때 수열 사이사이마다 사칙연산을 넣고, 나오는 값의 최댓값, 최솟값들을 알아내는 문제입니다.

 

단, 사칙연산의 법칙인 * / 우선법칙은 없고, 앞에서부터 순서대로 차례차례 계산합니다.

 

ex) (2 + 2 * 3 / 2) ->  (4 * 3 / 2) -> (12 / 2) -> 6

---

🔔 Kick Point :

DFS로 사칙연산을 순열의 경우의 수를 구하고, Cal() 함수를 통하여, 값을 계산해줬습니다.

 

 

 

++ 추가로 숏코딩 하신분의 코드를 봤는데, 정말 간단하고 명료헤서 깜짝놀랐씁니다. 제 코드 아래에 기재할게요

 

 

---

🔔 Code :

#include <iostream>
using namespace std;

int nArr[11]; // 수열
int oArr[10]; // 사칙연산 수열
int oper[4]; // operator 0: ADD, 1: SUB , 2: MUL, 3: DIV

int oArrDfs[10];
bool isVisited[10];

int n;
int MIN = 1000000000; // default 10억
int MAX = -1000000000;

// Input
void Input(int n) {
	for (int i = 0; i < n; i++) cin >> nArr[i];
	for (int i = 0; i < 4; i++) cin >> oper[i];

	int idx =0;
	for (int i = 0; i < 4; i++) {
		
		for (int j = 0; j < oper[i]; j++) oArr[idx + j] = i;
		idx += oper[i];
	}
	
}

// calculate
int Cal() {
	int tmp = 0;
	int k = nArr[0];

	while (tmp < (n-1)) {
		switch (oArrDfs[tmp])
		{
		case 0:
			k += nArr[tmp + 1];
			break;
		case 1:
			k -= nArr[tmp + 1];
			break;
		case 2:
			k *= nArr[tmp + 1];
			break;
		case 3:
			k /= nArr[tmp + 1];
			break;
		}
		++tmp;
	}
	return k;
}

void DFS(int cnt) {
	if (cnt == (n - 1)) {
		// cal 후, 최댓값 최솟값 비교
		int tmp = Cal();
		MAX = MAX < tmp ? tmp : MAX;
		MIN = MIN > tmp ? tmp : MIN;

		return;
	}

	for (int i = 0; i < (n - 1); i++) {

		if (!isVisited[i]) {
			isVisited[i] = true;
			oArrDfs[cnt] = oArr[i];
			DFS(cnt + 1);
			isVisited[i] = false;
		}
	}
}


int main() {
	cin >> n;
	Input(n);
	DFS(0);

	cout << MAX << endl;
	cout << MIN << endl;
}


// DFS - permutation

---

더 간단명료한 코드

#include <iostream>
using namespace std;

/* more short coding, second way */
int add, sub, mul, Div;
int nArr[11], n, MAX = -1000000000, MIN = 1000000000;

void DFS(int cnt, int result) {
	if (cnt == n) {
		MAX = MAX < result ? result : MAX;
		MIN = MIN > result ? result : MIN;
	}
	else {
		if(add) {
			add--;
			DFS(cnt + 1, result + nArr[cnt]);
			add++;
		}
		if(sub) {
			sub--;
			DFS(cnt + 1, result - nArr[cnt]);
			sub++;
		}
		if(mul) {
			mul--;
			DFS(cnt + 1, result * nArr[cnt]);
			mul++;
		}
		if(Div) {
			Div--;
			DFS(cnt + 1, result / nArr[cnt]);
			Div++;
		}
	}
}

int main() {

	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> nArr[i];
	cin >> add >> sub >> mul >> Div;
	DFS(1, nArr[0]);

	cout << MAX << '\n' << MIN;
}

 

DFS 안에서, if문 조건식을 통하여, 사칙연산의 방법을 순환하였다는 점이 굉장히 깔끔하고 좋았습니다. 그러면서 계산까지 한번에 해서 올려주는게 간단명료하군요