BOJ 14888 : 연산자 끼워넣기

#BOJ 14888 : 연산자 끼워넣기

14888번: 연산자 끼워넣기

#풀이

 

백트래킹을 이용하여 연산자를 하나씩 넣어보며 가장 큰 수와 가장 작은 수를 출력하는 문제이다,

 

나는 먼저 연산자를 입력받을 때 2 0 1 0 이면 벡터에다가 +,+,* 이렇게 저장하고

 

순열을 구할 수 있는 next_permutation을 사용했다.

 

do while 문을 통해 구할 수 있다.

 

#코드

#include<bits/stdc++.h>

using namespace std;
int n;
int arr[12];
vector<int> op; // +, -, *, /
int op_num[12];
int max_ans = -0x7f7f7f7f;
int min_ans = 0x7f7f7f7f;;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >>n;
	for(int i = 0; i <n; i++){
		cin >>arr[i];
	}
	for(int i = 1; i <= 4;i++){
		int num;
		cin >> num;
		for(int j = 0; j <num; j++){
			op.push_back(i);
		}
	}
		
	do{
		int ans = arr[0];
		int op_idx = 0;
		for(int i = 1; i < n; i++){
			if(op[op_idx] == 1){
				ans = ans + arr[i];
			}
			
			if(op[op_idx] == 2){
				ans = ans - arr[i];
			}
			
			if(op[op_idx] == 3){
				ans = ans * arr[i];
			}
			
			if(op[op_idx] == 4){
				ans = ans / arr[i];
			}
			op_idx++;
		
		}
		if(max_ans < ans)
			max_ans = ans;
		if(min_ans > ans)
			min_ans = ans;			
	
	}while(next_permutation(op.begin(), op.end()));
	
	cout << max_ans<<'\n';
	cout << min_ans<<'\n';
	
	return 0;
}