[SWEA 4008번] 숫자 만들기 :: 늦깎이 IT

[4008. [모의 SW 역량테스트] 숫자 만들기 URL]

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH&categoryId=AWIeRZV6kBUDFAVH&categoryType=CODE

이 문제는 백준의 연산자 끼워넣기 문제와 100% 같다.

2019/03/12 - [알고리즘 문제/백준(BOJ)] - [백준 14888번] 연산자 끼워넣기 (JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Solution {
 
    public static int tCase, N, minVal, maxVal;
    public static int[] operator, operand;
    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 NumberFormatException, IOException {
 
        tCase = Integer.parseInt(br.readLine());
 
        for (int t = 1; t <= tCase; t++) {
 
            minVal = Integer.MAX_VALUE;
            maxVal = Integer.MIN_VALUE;
            N = Integer.parseInt(br.readLine());
            operator = new int[4];
            operand = new int[N];
 
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < 4; i++)
                operator[i] = Integer.parseInt(st.nextToken());
 
            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++)
                operand[i] = Integer.parseInt(st.nextToken());
 
            dfs(1, operand[0]);
            System.out.println("#" + t + " " + (maxVal - minVal));
        }
    }
 
    public static void dfs(int depth, int totalVal) {
 
        if (depth >= N) {
            maxVal = Math.max(maxVal, totalVal);
            minVal = Math.min(minVal, totalVal);
            return;
        }
 
        for (int i = 0; i < 4; i++) {
 
            if (operator[i] > 0) {
                operator[i] -= 1;
                switch (i) {
                case 0:
                    dfs(depth + 1, totalVal + operand[depth]);
                    break;
                case 1:
                    dfs(depth + 1, totalVal - operand[depth]);
                    break;
                case 2:
                    dfs(depth + 1, totalVal * operand[depth]);
                    break;
                case 3:
                    dfs(depth + 1, totalVal / operand[depth]);
                    break;
                }
                operator[i] += 1;
            }
 
        }
 
    }
 
}