백준 : 16637

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

16637번: 괄호 추가하기

 

package com.ssay.algo;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class B16637 {
	static boolean check[];
	static int N;
	static char[] arr;
	static int maxValue;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr = br.readLine().toCharArray();

		check = new boolean[N];
		maxValue = Integer.MIN_VALUE;

		DFS(0);
		System.out.println(maxValue);

	}

	public static void DFS(int start) {
		String[] result = new String[N];
		int cnt = 0;
		for (int i = 0; i < N; i++) {
			if (check[i]) {
				int tmp = 0;
				if (arr[i + 1] == '+') {
					tmp = (arr[i] - '0') + (arr[i + 2] - '0');

				} else if (arr[i + 1] == '*') {
					tmp = (arr[i] - '0') * (arr[i + 2] - '0');

				} else if (arr[i + 1] == '-') {
					tmp = (arr[i] - '0') - (arr[i + 2] - '0');

				}
				result[cnt++] = String.valueOf(tmp);
				i += 2;
			} else {
				result[cnt++] = String.valueOf(arr[i]);
			}

		}

		int sum = Integer.parseInt(result[0]);
		for (int n = 1; n < cnt - 1; n = n + 2) {
			if (result[n].charAt(0) == '+') {
				sum = sum + Integer.parseInt(result[n+1]);
			} else if (result[n].charAt(0) == '*') {
				sum = sum * Integer.parseInt(result[n+1]);

			} else if (result[n].charAt(0) == '-') {
				sum = sum - Integer.parseInt(result[n+1]);
			}
		}
		if (maxValue < sum) {
			maxValue = sum;
		}

		for (int i = start; i < N - 2; i += 2) {
			check[i] = true;
			DFS(i + 4);
			check[i] = false;
		}

	}
}