14888번-연산자 끼워넣기

/*
수와 수 사이에 끼워넣을 수 있는 n-1개 연산자 있음. n개 숫자 있음. 
숫자는 변경 불가. 
식의 계산은 연산자 우선 순위를 무시하고, 앞에서부터 진행되어야 한다. 
나눗셈은 정수 나눗셈으로 몫만 취한다. 
음수를 양수로 나눌 때는 양수로 바꾼 후 몫을 음수로 한 것. 
*/
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int n,x;
int num[15];
int num_copy[15];
vector<int> oper;
int result;

//차례대로 +:0  -:1  x:2  %:3 개수 

int cal(int x,int y,int op) {
	if (op == 0) {
		return x + y;
	}
	if (op == 1) {
		return x - y;
	}
	if (op == 2) {
		return x * y;
	}
	if(op==3){
		return x / y;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;

	for (int i = 0; i < n; i++)cin >> num[i];

	//차례대로 +:0  -:1  x:2  %:3 개수 
	for (int i = 0; i < 4; i++) {
		cin >> x;
		while (x--) {
			oper.push_back(i);
		}
	}

	int min_num = 0x7f7f7f7f;
	int max_num = -0x7f7f7f7f;

	do {
		for (int i = 0; i < n; i++) {
			num_copy[i] = num[i];
		}
		for (int i = 0; i < (n - 1); i++) {
			num_copy[i + 1] = cal(num_copy[i], num_copy[i + 1], oper[i]);
		}
		max_num = max(num_copy[n-1], max_num);
		min_num = min(num_copy[n-1], min_num);

	} while (next_permutation(oper.begin(), oper.end()));

	cout << max_num << '\n' << min_num;
}

next_permutation으로 모든 경우의 수를 돌았다. 

처음엔 틀렸습니다가 나왔는데, max_num을 0으로 둬서 음수값이 최대일 경우를 고려하지 못했다. 

실전에서도 주어진 테스트 케이스를 통과했다고 안심하지 말고 다른 경우를 충분히 고려해봐야한다.!!!

다른 풀이 

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

int n;
int num[102];
int cal[4];
int mx = -0x7f7f7f7f;
int mn = 0x7f7f7f7f;

void func(int ans, int k){
  if(k == n){
    mx = max(mx, ans);
    mn = min(mn, ans);
    return;
  }

  for(int i = 0; i < 4; i++){
    if(!cal[i]) continue;
    cal[i]--;
    if(i == 0) func(ans + num[k], k+1);
    else if(i == 1) func(ans - num[k], k+1);
    else if(i == 2) func(ans * num[k], k+1);
    else if(i == 3) func(ans / num[k], k+1);
    cal[i]++;
  }
}

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n;
  for(int i = 0; i < n; i++) cin >> num[i];
  for(int i = 0; i < 4; i++) cin >> cal[i];
  func(num[0], 1);
  cout << mx << '\n' << mn << '\n';
}