[ 백준 14888 ] 연산자 끼워넣기 C++ DFS 풀이

# 문제링크

www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

이것도 삼성 기출이라는데 실버등급이다. 난이도가 복불복인가.. 암튼 숫자 위치는 바뀌지 않고, 연산자 위치만 바뀐다. 연산자의 개수가 최대 10개라서 그냥 모든 경우의 수를 계산해보면 된다. DFS로 구현했다.

 

문제 예시에서 경우의 수 60가지라고 했는데, 심심해서 한 번 모든 경우의 수를 출력해보았다.

제출 코드는 맨 아래에 있다.

 

# 1
+ + - * /
# 2
+ + - / *
# 3
+ + * - /
# 4
+ + * / -
# 5
+ + / - *
# 6
+ + / * -
# 7
+ - + * /
# 8
+ - + / *
# 9
+ - * + /
# 10
+ - * / +
# 11
+ - / + *
# 12
+ - / * +
# 13
+ * + - /
# 14
+ * + / -
# 15
+ * - + /
# 16
+ * - / +
# 17
+ * / + -
# 18
+ * / - +
# 19
+ / + - *
# 20
+ / + * -
# 21
+ / - + *
# 22
+ / - * +
# 23
+ / * + -
# 24
+ / * - +
# 25
- + + * /
# 26
- + + / *
# 27
- + * + /
# 28
- + * / +
# 29
- + / + *
# 30
- + / * +
# 31
- * + + /
# 32
- * + / +
# 33
- * / + +
# 34
- / + + *
# 35
- / + * +
# 36
- / * + +
# 37
* + + - /
# 38
* + + / -
# 39
* + - + /
# 40
* + - / +
# 41
* + / + -
# 42
* + / - +
# 43
* - + + /
# 44
* - + / +
# 45
* - / + +
# 46
* / + + -
# 47
* / + - +
# 48
* / - + +
# 49
/ + + - *
# 50
/ + + * -
# 51
/ + - + *
# 52
/ + - * +
# 53
/ + * + -
# 54
/ + * - +
# 55
/ - + + *
# 56
/ - + * +
# 57
/ - * + +
# 58
/ * + + -
# 59
/ * + - +
# 60
/ * - + +

 

# 제출 코드 

 

# include <cstdio>
using namespace std;

int N;
int A[12];
int B[4];
int max, min;
int chk[11];

// B[0] : + 의 수 
// B[1] : - ..
// B[2] : * ..
// B[3] : / ..

void Calc() {
	int tmp = A[0];
	for (int i = 1; i < N; i++) {
		switch (chk[i]) {
		case 0: tmp += A[i]; break;
		case 1: tmp -= A[i]; break;
		case 2: tmp *= A[i]; break;
		case 3: tmp /= A[i]; break;
		}
	}
	if (tmp > max) max = tmp;
	if (tmp < min)min = tmp;
}
void DFS(int node) {
	if (node == N) {
		Calc();
		return;
	}
	for (int i = 0; i < 4; i++) {
		if (B[i] == 0)continue;
		chk[node] = i;
		B[i]--;
		DFS(node + 1);
		B[i]++;
		chk[node] = 0;
	}
}

int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
		scanf("%d", &A[i]); // 수 
	for (int i = 0; i < 4; i++)
		scanf("%d", &B[i]); // 연산자 

	max = -0x7fffffff;
	min = 0x7fffffff;

	DFS(1);

	printf("%d\n", max);
	printf("%d\n", min);
}