백준 14888번 연산자끼워넣기 JAVA

백트래킹을 이해했다면 어렵지 않은 문제다.

백트래킹은 기본적으로 dfs에서 깊이를 들어가다가 깊이 끝까지 들어가면 리턴해서 stack에서 pop하고 거기서 다른 선택지가 있다면 다시 그곳을 탐색해서 전체 탐색을 하는 방식이다.

연달아 두문제를 푸니까 이제 좀 감이 오는 느낌..

import java.io.*;
import java.util.*;


public class Main {
    static int[] numbers;
    static int MAX=-999999999;
    static int Min=999999999;
    static int n;
    public static void dfs(int[] opers, int sum,int point){

        if(point==n){
            MAX=Math.max(MAX,sum);
            Min=Math.min(Min,sum);
            return;
        }


        if(opers[0]!=0){
            opers[0]-=1;//이미 계산한 연산자 빼고 전달
            dfs(opers,sum+numbers[point],point+1);
            opers[0]+=1;//백트래킹을 위해 다시 복원
        }
        if(opers[1]!=0){
            opers[1]-=1;
            dfs(opers,sum-numbers[point],point+1);
            opers[1]+=1;
        }
        if(opers[2]!=0){
            opers[2]-=1;
            dfs(opers,sum*numbers[point],point+1);
            opers[2]+=1;
        }
        if(opers[3]!=0){
            opers[3]-=1;
            dfs(opers,sum/numbers[point],point+1);
            opers[3]+=1;
        }

        return;//모든 깊이를 탐색하면 되돌림
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        numbers = new int[n];
        int[] oper = new int[4];
        String temp = br.readLine();
        st = new StringTokenizer(temp);
        int Now=0;
        int i=0;

        while (st.hasMoreTokens()){
            numbers[i++]=Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        i=0;
        while (st.hasMoreTokens()){
            oper[i++]=Integer.parseInt(st.nextToken());
        }


        dfs(oper,numbers[0],1);


        bw.write(Integer.toString(MAX));
        bw.newLine();
        bw.write(Integer.toString(Min));
        bw.flush();
        bw.close();
    }
}