[삼성SW역량테스트/DFS] 14888 연산자 끼워 넣기

문제를 보면 알겠지만 수를 하나씩 추가해 가면서 모든 경우의 수에 대해 다 해봐야 되는 문제이다. 따라서

DFS를 쓰면 해결할 수 있다.

위 처럼 수를 하나씩 추가해가면서 모든 경우의수에 대해서 DFS를 하면 되는데

맨 마지막 깊이에서 최대값, 최소값을 구해야 하므로

dfs를 해 나가면서 계속 기록해야 하는 정보는 트리의 깊이, 현재 깊이 까지의 누적값, + - * / 연산자의 남은 횟수

이렇게 3가지 이다. 배열의 경우 call by value로 매개변수를 전달해야 각 DFS흐름별로 연산자의 남은 횟수가 기록이 되는데 그냥 전달할 경우 call by reference로 전달 되기 때문에 연산자의 남은 개수가 저장된 op에 담긴 정보들을 임시배열인 tempop에 옮겨 담고 나서 다음 깊이로 이동하게끔 만들었다.

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int n;
int input[101];
int op[4];
long long MAX,MIN;
 
void DFS(long long num,int* op,int cnt){ //num은 누적수 cnt는 DFS의 깊이
    if(cnt == n-1){ // 연산자의 개수는 숫자보다 1개 적고 그때 최대,최소를 구해야함.
        if(num>=MAX)
            MAX=num;
        if(num<=MIN)
            MIN=num;
        return;
    }
    
    long long temp = input[cnt+1];
    int* tempop;
    for(int i=0; i<4; i++){
        
        tempop = new int[4];
        for(int i=0; i<4; i++)
            tempop[i] = op[i];
        
        if(tempop[i] != 0){
            switch(i){
                case 0:
                    tempop[0]--;
                    DFS(num+temp,tempop,cnt+1);
                    break;
                case 1:
                    tempop[1]--;
                    DFS(num-temp,tempop,cnt+1);
                    break;
                case 2:
                    tempop[2]--;
                    DFS(num*temp,tempop,cnt+1);
                    break;
                case 3:
                    tempop[3]--;
                    DFS(num/temp,tempop,cnt+1);
                    break;
            }
            
        }
    }
    delete[] tempop;
    
}
 
int main(){
    cin>>n;
    for(int i=0; i<n; i++)
        cin>>input[i];
    for(int i=0; i<4; i++)
        cin>>op[i];
    
    
    MAX = -1000000000;
    MIN = 1000000000;
    DFS(input[0],op,0);
    cout<<MAX<<endl<<MIN<<endl;
    
    return 0;
}