(14888) 연산자 끼워넣기

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

단계별로 풀어보기

20단계(백트래킹) 7번째

 

 

 

결국 백트래킹으로 구하고 싶은 건 n-1개의 연산자를 나열하는 경우이다. 이후 계산은 적절히 구현하면 된다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;
#define INF 1000000000

int main() 
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, maxval= -INF, minval= INF;
  
  cin >> n;
  
  vector<int> num(n), ar(4), v;
  
  for(int i=0;i<n;i++)  cin >> num[i];
  for(int i=0;i<4;i++)  cin >> ar[i];
  
  auto calc= [&](){
    int val= num[0];
    
    for(int i=0;i<n-1;i++){
      switch(v[i]){
        case 0:
          val=val+num[i+1];
          break;
        case 1:
          val=val-num[i+1];
          break;
        case 2:
          val=val*num[i+1];
          break;
        case 3:
          val=val/num[i+1];
          break;
      }
    }
    
    maxval= max(maxval, val);
    minval= min(minval, val);
  };
  
  auto func= [&](auto self, int depth) -> void {
    if(depth==n-1){
      calc();
      return;
    }
    
    for(int i=0;i<4;i++){
      if(!ar[i])  continue;
      
      ar[i]--;
      v.push_back(i);
      self(self, depth+1);
      ar[i]++;
      v.pop_back();
    }
  };
  
  func(func, 0);
  
  cout << maxval << "\n" << minval;
  
  return 0;
}