[백준/C++]14888번_연산자 끼워넣기

문제는 다음과 같습니다.

문제를 읽자마자, 연산자에 대해서 dfs를 수행하면 바로 끝나겠다라고 생각하고 코드를 짰습니다.

배열을 이용하여
💡연산자는 +, -, *, % 에 대해서 각각 인덱스 0, 1, 2, 3 값으로 나타내고,
💡해당 연산자의 개수를 인덱스의 값으로 나타냈습니다.

전체 코드는 다음과 같습니다.🙆🏻‍♀️

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

int n;
int a[11]={0, };
int op[4]={0, };
int res[10]={0, };
long long int max_sum = LLONG_MIN;
long long int min_sum = LLONG_MAX;

void dfs(int idx){
    if(idx==n-1){ // 연산자 개수 다 채워졌을 때
        long long int sum=a[0];
        for(int i=0; i<n-1; i++){
            if(res[i]==0) sum += a[i+1];
            if(res[i]==1) sum -= a[i+1];
            if(res[i]==2) sum *= a[i+1];
            if(res[i]==3) sum /= a[i+1];
        }
        // 최대값, 최소값 갱신시키기
        max_sum = max(max_sum, sum);
        min_sum = min(min_sum, sum);
    }
    else{
        for(int i=0; i<4; i++){
            if(op[i]>0){ // 연산자가 존재하는 경우
                res[idx]=i;
                op[i]-=1;
                dfs(idx+1);
                op[i]+=1; // 복원
            }
        }
    }
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  int tmp;
  cin>>n;
  for(int i=0; i<n; i++) cin>>a[i];
  for(int i=0; i<4; i++) cin>>op[i];

  dfs(0);

  cout<<max_sum<<"\n"<<min_sum<<"\n";
  return 0;
}

좋은 웹페이지 즐겨찾기