boj 16637: 괄호 추가하기

문제 조건

• 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다.
• 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다. (짝수번째는 숫자, 홀수번째는 연산 기호)
• 연산자는 +, -, * 중 하나이다.
• 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다. 단, 괄호는 중첩되면 안된다.

수식의 길이 1 ≤ N ≤ 19이므로 dfs를 이용하여 완전 탐색을 해도 시간 초과가 나지 않을 것이다.

괄호를 묶는 방법은 (a+b)+c, a+(b+c) 두 가지 방법으로 나누어 계산한다.

import java.util.*;

public class Main {
	public static long max = Integer.MIN_VALUE;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		String s = in.next();
		char[] expression = s.toCharArray();

		if (n == 1) {
			System.out.println(s);
		} else {
			dfs(expression[0] - '0', 1, expression);
			System.out.println(max);
		}
	}

	public static void dfs(long result, int index, char[] expression) {
		if (index + 1 >= expression.length) {
			max = Math.max(max, result);
			return;
		}

		// (a+b)+...
		long resultFront = calculate(result, expression[index], expression[index + 1]);
		dfs(resultFront, index + 2, expression);

		// a+(b+c)+...
		if (index + 3 < expression.length) {
			long resultBack = calculate(expression[index + 1], expression[index + 2], expression[index + 3]);
			dfs(calculate(result, expression[index], resultBack), index + 4, expression);
		}

	}

	public static long calculate(long a, char op, long b) {
		switch (op) {
		case '*':
			return a * b;
		case '+':
			return a + b;
		case '-':
			return a - b;
		}
		return 0L;
	}

	public static long calculate(long a, char op, char b) {
		return calculate(a, op, (long) (b - '0'));
	}

	public static long calculate(char a, char op, char b) {
		return calculate((long) (a - '0'), op, (long) (b - '0'));
	}
}