백준 15658 JAVA

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

15658번: 연산자 끼워넣기 (2)

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


public class Main {
    static int n;  //첫째줄 수열의 개수
    static int[] nums;  //수열을 담을 배열 nums
    static int[] operator; //수식을 담을 배열 operator
    static int result_min = Integer.MAX_VALUE;  //최대값
    static int result_max = Integer.MIN_VALUE;  //최소값

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());  //첫째줄 수열의 개수
        nums = new int[n];  //수열을 담을 배열 nums

        StringTokenizer st = new StringTokenizer(br.readLine()); //두번째 줄 
        for(int i=0; i<n; i++){
            nums[i] = Integer.parseInt(st.nextToken());  // 수열 분리후 nums 배열에 저장
        }

        operator = new int[4];  // 셋째 줄에는 합이 N-1보다 크거나 같고, 4N보다 작거나 같은 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수를 담을 배열 operator
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<4; i++){
            operator[i] = Integer.parseInt(st.nextToken());
        }
        
        dfs(1, nums[0]);  

        System.out.println(result_max);
        System.out.println(result_min);
    }

    public static void dfs(int idx, int sum){
        if(idx==n){  //깊이가 수열의 개수와 갔다면
            result_min = Math.min(result_min, sum);  //최대값
            result_max = Math.max(result_max, sum); //최소값
            return;
        }

        for(int i=0; i<4; i++){
            if(operator[i] == 0) continue;  //사용할 수 있는 수식이 없는 경우 continue
            operator[i]--; //수식개수 하나 제거 
            switch (i){  //순서 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수
                case 0:
                    dfs(idx + 1, sum + nums[idx]);  //깊이+1 추가 
                    break;
                case 1:
                    dfs(idx + 1, sum - nums[idx]);
                    break;
                case 2:
                    dfs(idx + 1, sum * nums[idx]);
                    break;
                case 3:
                    dfs(idx + 1, sum / nums[idx]);
                    break;
            }
            operator[i]++;  //수식을 사용하고 나서는 수식 개수를 원상복귀 시켜야됨
        }


    }

}

\