[백준 14888] 연산자 끼워넣기

 

숫자 사이사이에 들어갈 기호를 모두 대입해보며 진행해야 한다.

일반적인 완전탐색으로는 구현하기 힘들고 재귀를 이용한 탐색을 사용해야 한다.

백트래킹 기법을 이용하여 앞서 대입한 연산자도 바꿀수 있게했다.

 

 

public class Main {
 
    static int n;
    static int a[];
    static int oper[];
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        n = sc.nextInt();
        a = new int[n];
        oper = new int[4];
        for(int i=0; i<n; i++)
            a[i] = sc.nextInt();
        
        for(int i=0; i<4; i++)
            oper[i] = sc.nextInt();
        
        dfs(1, a[0]);
        
        System.out.println(max);
        System.out.println(min);
    }
    
    public static void dfs(int cnt, int n) {
        if(cnt == Main.n) {
            max = Math.max(max, n);
            min = Math.min(min, n);
            return;
        }
        
        if(oper[0] > 0) {
            oper[0]--;
            dfs(cnt + 1, n + a[cnt]);
            oper[0]++;
        }
        
        if(oper[1] > 0) {
            oper[1]--;
            dfs(cnt + 1, n - a[cnt]);
            oper[1]++;
        }
        
        if(oper[2] > 0) {
            oper[2]--;
            dfs(cnt + 1, n * a[cnt]);
            oper[2]++;
        }
        
        if(oper[3] > 0) {
            oper[3]--;
            dfs(cnt + 1, n / a[cnt]);
            oper[3]++;
        }
    }
}