[백준] 16637 괄호 추가하기 - 완전탐색(BruteForce) + DFS(깊이우선탐색) + 연산자 JAVA

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

16637번: 괄호 추가하기

코드설명

DFS를 활용하여 연산자를 고려하여 완전탐색을 진행하는 문제입니다.

 

문제에서 헷갈리는점은,

(A + B) + C는 어떻게 계산하는가가 헷갈리는데,

A + B 는 괄호가 없는경우 항상 먼저 시작하기에, 해당 사항은 이후의 괄호 처리시 자동으로 계산되는 로직입니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
 
public class Main {
	
	public static int N;
	public static ArrayList<Integer> num = new ArrayList<>();
	public static ArrayList<Character> operand = new ArrayList<>();
	public static int answer = Integer.MIN_VALUE;
	
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	
    	String str = br.readLine();
    	for(int i=0;i<N;i++) {    		
    		if(i%2 == 0) { // 짝수라면 (문자 숫자를 숫자로 변환하기 위해 - '0' 처리)
    			num.add(str.charAt(i) - '0');
    		}else if(i%2 == 1) { // 홀수라면
    			operand.add(str.charAt(i));
    		}
    	}
    	simulate(num.get(0), 0);
    	System.out.println(answer);
    }
    
    //현재 인덱스, 합
    public static void simulate(int sum, int operandIdx) {
    	if(operandIdx >= operand.size()) {
    		answer = Math.max(answer, sum);
    		return ;
    	}
    	
    	//괄호 없는경우 A + B
    	int rs1 = calculate(operand.get(operandIdx), sum, num.get(operandIdx + 1));
    	simulate(rs1, operandIdx + 1);
    	
    	//괄호 있는경우 ( 옆의 연산결과에 괄호를 붙이는것 )  A + (B + C)
    	if(operandIdx + 1 < operand.size()) {
    		int rs2 = calculate(operand.get(operandIdx + 1), num.get(operandIdx + 1), num.get(operandIdx + 2));
    		
    		int rs3 = calculate(operand.get(operandIdx), sum, rs2);
    		simulate(rs3, operandIdx + 2);
    	}
    }
    
    public static int calculate(char operand, int a, int b) {
    	switch(operand) {
    	case '+':
    		return a + b;
    	case '-':
    		return a - b;
    	case '*':
    		return a * b;
    	}
    	return 999;
    }
   
    
    
}