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

문제

풀이

이 문제는 재귀적 완전탐색(DFS) + 백트래킹 문제이다.연산자를 차례대로 방문하면서 끼워넣어 완전한 식과 그에대한 total 값을 낸 다음 , 사용하였던 연산자 개수를 회복하면서 다른 순서 방식을 통해 다시 반복하는 식으로 하면 된다. 

 

 

import java.util.*;
import java.io.*;
 
public class Main{
    static int N;
    static int[] arr;
    static int[] operator;
    static int min,max;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::valueOf).toArray(); // 피 연산자 입력
        operator = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::valueOf).toArray(); // 연산자 입력
        min=Integer.MAX_VALUE; max=Integer.MIN_VALUE;
        dfs(arr[0],0);
 
        System.out.println(max);
        System.out.println(min);
    }
    public static void dfs(int total,int index){
 
        if(index == N-1){
            min = Math.min(min,total);
            max = Math.max(max,total);
            return;
        }
 
        for(int i=0;i<operator.length;i++){
            if(operator[i] <= 0) //해당 연산자의 남은 갯수가 없으면 pass
                continue;
            operator[i]--; // 연산자 1개 소모
            int nextIndex = index+1; // 연산될 피 연산자
            int next=0; // 다음 total 값
            if(i==0){
                next = total+arr[nextIndex];
                dfs(next,nextIndex);
            }
            if(i==1){
                next = total-arr[nextIndex];
                dfs(next,nextIndex);
            }
            if(i==2){
                next = total*arr[nextIndex];
                dfs(next,nextIndex);
            }
            if(i==3) {
                next = total/arr[nextIndex];
                dfs(next,nextIndex);
            }
            operator[i]++; // 소모한 연산자 1개 다시 회복
        }
    }
}