연산자 끼워넣기 C++ - 백준 14888

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

이 문제는 백트래킹 문제이다.

arr에 숫자들을 저장하고, dfs를 사용하여 현재의 최댓값, 최솟값보다 초과, 미만이면 저장하는 방법으로 작성했다.

코드는 다음과 같다. (스택을 사용하지 않은 더 간결한 예제는 이 코드 밑에 있다.)

#include <bits/stdc++.h>
#define FASTIO ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define MAX 12
#define INFI 1000000000
using namespace std;

int arr[MAX];
int counts[4]; //plus minus multiple divide
int used[4];
int N;
int maxi=-1*INFI;
int mini=INFI;
int cur;
stack<int> s;

void dfs(int cnt){
	if(cnt==N-1){
		if(maxi<cur){
			maxi=cur;
		}
		if(mini>cur){
			mini=cur;
		}
		return;
	}
	
	if(used[0]<counts[0]){
		used[0]++;
		s.push(cur);
		cur+=arr[cnt+1];
		dfs(cnt+1);
		used[0]--;
		cur=s.top();
		s.pop();
	}
	if(used[1]<counts[1]){
		used[1]++;
		s.push(cur);
		cur-=arr[cnt+1];
		dfs(cnt+1);
		used[1]--;
		cur=s.top();
		s.pop();
	}
	if(used[2]<counts[2]){
		used[2]++;
		s.push(cur);
		cur*=arr[cnt+1];
		dfs(cnt+1);
		used[2]--;
		cur=s.top();
		s.pop();
	}
	if(used[3]<counts[3]){
		used[3]++;
		s.push(cur);
		cur/=arr[cnt+1];
		dfs(cnt+1);
		used[3]--;
		cur=s.top();
		s.pop();
	}
}

int main(){
	FASTIO
	cin >> N;
	for(int i=0;i<N;i++){
		cin >> arr[i];
	}
	for(int i=0;i<4;i++){
		cin >> counts[i];
	}
	cur=arr[0];
	dfs(0);
	cout << maxi << '\n' << mini;
}

다음 코드는 스택을 없애고, 파라미터를 늘려 간결화한 코드이다.

#include <iostream>
#include <algorithm>
#define MAX 1000000000
using namespace std;

int maxi=-MAX;
int mini=MAX;
int arr[11];
int n;
int signs[4];

void solve(int x, int ind, int a, int b, int c, int d){
	if(ind==n-1){
		maxi=max(maxi,x);
		mini=min(mini,x);
		return;
	}
	
	if(a<signs[0]){
		solve(x+arr[ind+1],ind+1,a+1,b,c,d);
	}
	if(b<signs[1]){
		solve(x-arr[ind+1],ind+1,a,b+1,c,d);
	}
	if(c<signs[2]){
		solve(x*arr[ind+1],ind+1,a,b,c+1,d);
	}
	if(d<signs[3]){
		solve(x/arr[ind+1],ind+1,a,b,c,d+1);
	}
}

int main(){
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> arr[i];
	}
	for(int i=0;i<4;i++){
		cin >> signs[i];
	}
	solve(arr[0],0,0,0,0,0);
	cout << maxi << '\n' << mini;
}