[백준OJ] 14888번 연산자 끼워넣기

www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

---

-풀이-

기본적인 백트래킹을 이용하여 문제를 해결했다.

백트래킹을 이용하여 모든 경우의 수를 다 뒤져보며, 최댓값과 최솟값을 갱신해주었다.

문제에서 결과값과 중간값은 +10억이하 -10억 이상이라 해서 minR의 초기값을 +10억1, maxR의 초기값을 -10억1로 선언해주었다.

 

-시간복잡도-

모든 경우의수를 찾아보는것이므로, 분기마다 4개의 선택지가 생긴다. 따라서 O(4^n)이 된다.

 

-코드-

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

int arr[100];
int op[4];
int n, maxR=-1000000001,minR=1000000001;

void dfs(int ind,int sum,int n) {
	if (ind == n) {
		maxR = max(maxR, sum);
		minR = min(minR, sum);
		return;
	}
	for (int i = 0; i < 4; i++) {
		if (op[i] != 0) {
			op[i]--;
			if (i == 0) {
				dfs(ind + 1, sum + arr[ind],n);
			}
			else if (i == 1) {
				dfs(ind + 1, sum - arr[ind],n);
			}
			else if (i == 2) {
				dfs(ind + 1, sum * arr[ind],n);
			}
			else {
				dfs(ind + 1, sum / arr[ind],n);
			}
			op[i]++;
		}
	}
}

int main(){
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	for (int i = 0; i < 4; i++) {
		cin >> op[i];
	}
	dfs(1, arr[0],n);
	cout << maxR << "\n" << minR << "\n";
}