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

https://www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

 

 

 

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

public class Main{
    static int n; // 숫자 개수
    static int[] operator = new int[4]; // 연산자 배열
    static int[] number; // 숫자 배열
    static int max = Integer.MIN_VALUE;
    static int min = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n=Integer.parseInt(br.readLine());
        number = new int[n];

        st=new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<n; i++) number[i] = Integer.parseInt(st.nextToken());

        st=new StringTokenizer(br.readLine(), " ");
        for(int i=0; i<4; i++) operator[i] = Integer.parseInt(st.nextToken());

        dfs(number[0], 1);

        System.out.println(max);
        System.out.println(min);
    }

    public static void dfs(int num, int idx){
        if(idx == n){ // 모든 연산자를 사용했을 때
            max=Math.max(max,num);
            min=Math.min(min,num);
            return;
        }

        for(int i=0; i<4; i++){
            if(operator[i]>0){ // 연산자 개수가 1개 이상일 경우
                operator[i]--; // 해당 연산자 1 감소

                switch(i){
                    case 0: dfs(num+number[idx], idx+1); break;
                    case 1: dfs(num-number[idx], idx+1); break;
                    case 2: dfs(num*number[idx], idx+1); break;
                    case 3: dfs(num/number[idx], idx+1); break;
                }
                operator[i]++; // 재귀 호출 후에는 연산자 개수 복구
            }
        }
    }
}