[백준 14888번] 연산자 끼워넣기 :: 늦깎이 IT

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

모든 경우의 수를 모두 탐색하는 문제입니다.

DFS 탐색을 사용하였습니다.

[소스코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
 
    public static int N, minVal = Integer.MAX_VALUE, maxVal = Integer.MIN_VALUE;
    public static int[] temp, arr, expression;
    public static int[] dirX = new int[] { 0, 0, -1, 1 };
    public static int[] dirY = new int[] { 1, -1, 0, 0 };
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    public static void main(String[] args) throws Exception {
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        arr = new int[N];
        temp = new int[N - 1];
        expression = new int[4];
 
        st = new StringTokenizer(br.readLine());
        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++)
            expression[i] = Integer.parseInt(st.nextToken());
 
        dfs(1, arr[0]);
        System.out.println(maxVal);
        System.out.println(minVal);
    }
 
    public static void dfs(int depth, int totalVal) {
 
        if (depth > N - 1) {
            minVal = Math.min(minVal, totalVal);
            maxVal = Math.max(maxVal, totalVal);
            return;
        }
 
        for (int i = 0; i < 4; i++) {
 
            if (expression[i] > 0) {
                expression[i] -= 1;
                switch (i) {
                case 0:
                    dfs(depth + 1, totalVal + arr[depth]);
                    break;
                case 1:
                    dfs(depth + 1, totalVal - arr[depth]);
                    break;
                case 2:
                    dfs(depth + 1, totalVal * arr[depth]);
                    break;
                case 3:
                    dfs(depth + 1, totalVal / arr[depth]);
                    break;
                }
                expression[i] += 1;
            }
 
        }
 
    }
}