[백준 16637 Java] 괄호 추가하기

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
	/*
		base_pan		:	계산할 숫자들의 Array
		base_pan_sign	:	계산할 부호(+,-,*)
		input_sign_cnt	:	계산할 부호의 개수(계산 횟수)
		result			:	Int로 표현 가능한 최소의 정수를 초기값으로 가지며, 정답을 저장
	*/
	
	static int[] base_pan;
	static String[] base_pan_sign;
	static int input_sign_cnt;
	static int result = Integer.MIN_VALUE;
	
	/*
		calc(a, sign_index, b)	:	a와 b를 base_pan_sign[sign_index] 계산해 calc_result로 반환
	*/
	public static int calc(int a, int sign_index, int b) {
		
		int calc_result=0;
		
		if("+".equals(base_pan_sign[sign_index])) {
			calc_result = a+b;
		}else if("-".equals(base_pan_sign[sign_index])) {
			calc_result = a-b;
		}else {
			calc_result = a*b;
		}
		
		return calc_result;
	}
	
	public static void main (String[] args) throws java.lang.Exception
	{
		
		/*
			input_cnt		:	입력 1번째 값(숫자개수+부호개수)
			input_str		:	입력 2번째 값(수식)
			input_num_cnt	:	계산할 숫자의 개수
			input_sign_cnt	:	계산할 부호의 개수(계산 횟수), static
		*/
	
		Scanner sc = new Scanner(System.in);
		int input_cnt = Integer.parseInt(sc.next());
		String input_str = sc.next();
		
		int input_num_cnt=input_cnt/2+1;
		input_sign_cnt = input_num_cnt-1;
		
		base_pan = new int[ input_num_cnt ];
		base_pan_sign = new String[ input_sign_cnt ];
		
		// 입력받은 input_str를 숫자와, 부호로 나누어 base_pan, base_pan_sign에 각각 입력(58~70line)
		int start_str = 0;
		int input_num_cnt_i=0;
		int input_sign_cnt_i=0;
		for (int i=0;i<input_cnt;i++) {
			if( (input_str.charAt(i)=='+')||(input_str.charAt(i)=='-')||(input_str.charAt(i)=='*') ) {
				base_pan[input_num_cnt_i]=Integer.parseInt(input_str.substring(start_str,i));
				base_pan_sign[input_sign_cnt_i]=String.valueOf(input_str.charAt(i));
				start_str=i+1;
				input_num_cnt_i++;
				input_sign_cnt_i++;
			}
		}
		base_pan[input_num_cnt_i]=Integer.parseInt(input_str.substring(start_str,input_cnt));
		
		dfs(base_pan[0], 0);
		
		System.out.print(result);
		
		
	}
	
	public static void dfs(int pre_sum, int sign_index) {
		
		// input_sign_cnt만큼 계산이 되었다면 그 결과가 최대값인지 확인 후 result에 저장한다.
		if(sign_index==input_sign_cnt) {
			if(result<pre_sum) {
				result=pre_sum;
			}
			return;
		}
		
		// sign_index번째 계산을 한다.
		int post_sum = calc(pre_sum, sign_index, base_pan[sign_index+1]);
		
		dfs(post_sum, sign_index+1);
		
		// sign_index번째 계산보다 sign_index+1번째 계산을 먼저 한다.
		if( sign_index+1 < input_sign_cnt ) {
			post_sum = calc(base_pan[sign_index+1], sign_index+1, base_pan[sign_index+2]);
			post_sum = calc(pre_sum, sign_index, post_sum);
			
			dfs(post_sum, sign_index+2);
		}
		
		
	}
	
}