[Dev-Ping9] 백준 14888번 - 연산자 끼워넣기 (Java)

 

 

# 문제설명

 1. optimal 한 값을 두개 (최대, 최소) 구해야 한다.

 2. 2<=N<=11, 0<=A(i)<=100 이다.

 3. 부분구조를 이루지 않으므로, dp로는 구현이 어렵다.

 4. dfs 로 구현한 뒤, 더 이상 탐색 할 필요 없는 노드는 탐색하지 않는다. (Backtracking)

 

 

 

# 코드구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
    static long[] arr;
    static int[] opArr = new int[4];
    static long max, min;
    static int ans;

    static long doTheMath(long a, long b, int opIdx){
        if(opIdx ==1){ // plus
            return a+b;
        }else if(opIdx==2){ // minus
            return a-b;
        }else if(opIdx==3){ // multiply
            return a*b;
        }else{// divide
            if(a<0){
                return ((-1*a)/b) * (-1);
            }
            return a/b;
        }
    }

    static void dfs(int start, int n, int op, long result, int op1, int op2, int op3, int op4, int flag){
        if(start == n-1){
            max= Math.max(result,max);
            min= Math.min(result,min);
            return;
        }
        long judge = flag;

        //Backtracking
        if(op==1 && op1>0){//+
            op1--; 
            flag--;
            result = doTheMath(result, arr[start+1], op);
        }else if(op==2 && op2>0){
            op2--;
            flag--;
            result = doTheMath(result, arr[start+1], op);
        }else if(op==3 && op3>0){
            op3--; 
            flag--;
            result = doTheMath(result, arr[start+1], op);
        }else if(op==4 && op4>0){
            op4--;
            flag--;
            result = doTheMath(result, arr[start+1], op);
        }

        //DFS
        if(judge!=flag || start == -1){ 
            dfs(start+1, n, 1, result, op1,  op2, op3, op4,flag);
            dfs(start+1, n, 2, result, op1,  op2, op3, op4,flag);
            dfs(start+1, n, 3, result, op1,  op2, op3, op4,flag);
            dfs(start+1, n, 4, result, op1,  op2, op3, op4,flag);
        }
        
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        arr = new long[n];

        for(int i=0; i<n; i++){
            arr[i]= Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());    
        
        for(int i=0;i<4;i++){
            opArr[i] = Integer.parseInt(st.nextToken());
        }

        max=Long.MIN_VALUE;
        min=Long.MAX_VALUE;

        dfs(-1, n, -5, arr[0], opArr[0],opArr[1],opArr[2],opArr[3],504);

        System.out.println(max);
        System.out.println(min);
        //최대 최소
        // * 음수나눗셈 = 양수로 바꾼뒤 몫을 취하고, 그 몫을 음수로 바꾼다
        // * 나눗셈 = 정수나눗셈
        // * 연산자 우선순위 무시

    }
}


/*
2
0 3
0 1 0 0

3
0 3 0
0 2 0 0

*/