[세모] [알고리즘] 백준 14888 연산자끼워넣기 c++ // dfs, 순열

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

14888번: 연산자 끼워넣기

1.의사코드

 

2. 전체코드

v: 5 6(i+1)

a: +(i)

#include <bits/stdc++.h>

using namespace std;

int N,p,m,g,na,ret1=-1000000000 -1;
int ret2 = 1000000000+1;
vector<int> v;

//n번째자리, 들어갈연산
void dfs(int n, vector<char> a,int P,int M,int G,int NA) {
	if (n == N) {
		int sum = v[0];
		for (int i = 0; i < N-1; ++i) {
			if (a[i] == '+') {
				sum += v[i+1];
			}
			if (a[i] == '-') {
				sum -= v[i + 1];
			}
			if (a[i] == '*') {
				sum *= v[i + 1];
			}
			if (a[i] == '/') {
				sum /= v[i + 1];
			}
			
		}
		ret1 = max(ret1, sum);
		ret2 = min(ret2, sum);
		return;
	}
	if (P > p || M > m || G > g || NA > na) return;

	//+인경우
	a.push_back('+');
	dfs(n + 1, a,P+1,M,G,NA);
	a.pop_back();

	//-인경우
	a.push_back('-');
	dfs(n + 1, a, P , M+1, G, NA);
	a.pop_back();

	//*인경우
	a.push_back('*');
	dfs(n + 1, a, P , M, G+1, NA);
	a.pop_back();

	// /인경우
	a.push_back('/');
	dfs(n + 1, a, P, M, G, NA+1);
	a.pop_back();
}
int main() {
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; ++i) {
		int tmp;
		cin >> tmp;
		v.push_back(tmp);
	}
	cin >> p >> m >> g >> na;

	vector<char> v1;
	dfs(0, v1,0,0,0,0);
	cout << ret1<<"\n"<<ret2;
	return 0;
}

 

* 25.2.15. 2회독 내풀이

• N=11 -> 순열로 모든 경우의수 생성 // 11! = 3000만
• 해당 연산자의 갯수만큼 숫자를 v에담은후, 순열생성
• 이후 순열의 값에따라 +,-,*,/ 해주면서 ret값 갱신
• ret가 누적계산 저장의 역할을 해야함에 주의

#include<bits/stdc++.h>
using namespace std; 

int n,ret1= -1000000000-4 ,ret2=1000000000+4;
int a[14]; //숫자, 연산자 갯수[+, -, *, / ]
vector<int> v; //[0,1,2,3] :

int go() {
   int ret=a[0];
   for(int i=0;i<n-1;++i) {
      if(v[i]==0)
         ret+= a[i+1];
      if(v[i]==1)
         ret-= a[i+1];
      if(v[i]==2)
         ret*= a[i+1];
      if(v[i]==3)
         ret/= a[i+1];
   }
   return ret;
}

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
   
   cin>>n;
   for(int i=0;i<n;++i) {
      cin>>a[i];
   }
   for(int i=0;i<4;++i) {
      int tmp;
      cin>>tmp;
      while(tmp--) {
         v.push_back(i);
      }
   }

   do {
      // for(auto i : v) {
      //    cout<<i<<" ";
      // }cout<<"\n";
      int res = go();
      ret1=max(ret1,res);
      ret2=min(ret2,res);
   }while(next_permutation(v.begin(), v.end()));

   cout<<ret1<<"\n"<<ret2;
}

 

* 큰돌풀이

• dfs : 4^11 // (+ - * / ) 4가지경우, depth=11까지
• cur이 누적결과 저장소의 역할

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<vector>
#include<string.h>
using namespace std;  
int n;
int a[12], b[4];
int p, minu, mult, divi;
int ret = -1000000001;
int ret2 = 1000000001;
void go(int index, int cur, int plus, int minus, int mul, int div){ 
    //printf("%d\n", index);
    if(index == n - 1){
        ret = max(cur, ret);
        ret2 = min(ret2, cur);
        return; 
    }
    if(plus) go(index + 1, cur  + a[index + 1], plus - 1, minus, mul, div);
    if(minus) go(index + 1, cur - a[index + 1], plus, minus - 1, mul, div);
    if(mul) go(index + 1, cur * a[index + 1], plus, minus, mul - 1, div);
    if(div) go(index + 1, cur / a[index + 1], plus, minus, mul, div - 1);
    return;
}
int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i++){ 
        scanf("%d", &a[i]); 
    }    
    scanf("%d %d %d %d", &p, &minu, &mult, &divi);
    go(0, a[0], p, minu, mult, divi);
    printf("%d\n%d\n", ret,ret2);
    return 0; 
}