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

풀이

괄호가 중복된 것을 허용하지 않고, 연산자 우선순위가 동일하므로 왼쪽부터 계산하는 문제입니다.

 

연산자와 숫자를 나누어 담고

dfs를 활용해서, 케이스를 인덱스 기반으로

1. 괄호를 안친것으로 계산 과정

2. 괄호를 친것으로 계산 과정

두가지로 나누어서 진행했습니다.

 

첫번째 경우는 index, index + 1 를 연산과정을 하고 다음 dfs 

두번째 경우는 index + 1, index +2를 먼저 연산하고, 지금까지 계산한 것과 다시 또 연산하고 다다음 dfs 

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

public class Main {
	static int N, max=Integer.MIN_VALUE;
	static ArrayList<Integer> number = new ArrayList<>();
	static ArrayList<Character> operation = new ArrayList<>();
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		String input = br.readLine();
		for(int i = 0 ; i < N ; i++) {
			if(i % 2  == 0) number.add(input.charAt(i) -'0');
			else operation.add(input.charAt(i));
		}
		
		dfs(0, number.get(0));
		System.out.println(max);
	}
	
	private static void dfs(int index, int sum) {
		if(index >= N/2) {
			max = Math.max(sum, max);
			return;
		}
		// 그냥 진행 
		dfs(index + 1, calculate(index, sum, number.get(index+1)));
		
		// 괄호 치고 진행 
		if(index + 1 < N/2) {
			// 뒤에 괄호쳤다고 생각하고 계산 
			int num = calculate(index + 1, number.get(index + 1), number.get(index + 2));
			// 현재 연산자와 다음 괄호를 쳐서 우선 연산 한것을 계산 
			dfs(index + 2, calculate(index, sum, num));
		}
	}
	
	private static int calculate(int index, int a, int b) {
		char op = operation.get(index);
		int result = 0;
		if(op == '+') {
			result = a+b;
		}
		else if(op == '*') {
			result = a * b;
		}
		else if(op == '-') {
			result = a - b;
		}
		return result;
	}
	
}