백준 14888 (연산자 끼워넣기)

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

14888번: 연산자 끼워넣기

풀이

해당 문제는 DFS로 모든 경우의 수를 탐색하면서 MAX, MIN 값을 구하면 되는 문제이다.

1. 숫자 배열과, 연산자 기호를 넣을 배열을 동시에 운용하며 문제를 풀이

2. 재귀함수를 통해 level이 N값과 같아지면 return

3. 각 재귀시 for 루프는 연산자의 개수만큼 수행한다. and visit 배열을 사용하여 각 연산자가 사용되었다면 체크해 주어 다시 사용되지 않게 설정

#include <iostream>
#include <string>

using namespace std;

int nList[12];
int n;
int strn;
string oper;
int operCheck[100];

int maxx = INT_MIN;
int mins = INT_MAX;


void dfs(int level, int sum){
	if (level == n){
		if (sum > maxx) maxx = sum;
		if (sum < mins) mins = sum;
		return;
	}

	for (int i = 0; i < strn; ++i){
		if (operCheck[i] == 0){
			operCheck[i] = 1;
			if (oper[i] == '+'){
				dfs(level + 1, sum + nList[level]);
			}
			if (oper[i] == '-'){
				dfs(level + 1, sum - nList[level]);
			}
			if (oper[i] == '*'){
				dfs(level + 1, sum * nList[level]);
			}
			if (oper[i] == '/'){
				dfs(level + 1, sum / nList[level]);
			}
			operCheck[i] = 0;
		}
	}

}

int main(){
	//freopen_s(new FILE*, "tes.text", "r", stdin);
	cin >> n;
	for (int i = 0; i < n; ++i){
		cin >> nList[i];
	}

	for (int i = 0; i < 4; ++i){
		int tmp;
		cin >> tmp;
		for (int j = 0; j < tmp; ++j){
			if (i == 0){
				oper += '+';
			}
			if (i == 1){
				oper += '-';
			}
			if (i == 2){
				oper += '*';
			}
			if (i == 3){
				oper += '/';
			}
		}
	}

	strn = oper.length();
	dfs(1, nList[0]);

	printf("%d\n%d", maxx, mins);

}