괄호 추가하기

in Algorithm on 백준


백준 [16637] 괄호 추가하기

문제보기
Alt text

풀이

  • 주의사항 : ans의 초기화를 0이 아닌 -987654321 또는 Integer.MIN_VALUE로 해주어야 한다.
  • dfs() : 어떤 연산자에 괄호를 추가하거나 안할것인지 결정. 앞뒤 연산자에 괄호가 있다면 이중 괄호가 되어 괄호추가 불가.
  • solve() : 괄호가 결정된 후 괄호를 먼저 계산하고 이후 순서대로 계산. 이미 괄호때문에 계산된 연산자라면 앞의 계산된 값을 그대로 가져간다.

소스코드

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

public class Main {
	static int ans, N;
	static int[] num;
	static char[] operator;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		num = new int[N / 2 + 1];
		operator = new char[N / 2];
		String str = br.readLine();

		for (int i = 0; i < str.length(); i++) {
			if (i % 2 == 0)
				num[i / 2] = str.charAt(i) - '0';
			else
				operator[i / 2] = str.charAt(i);
		}

		ans = -987654321;
		dfs(new boolean[operator.length], 0);
		System.out.println(ans);
	}

  // 괄호 결정
	public static void dfs(boolean[] flag, int idx) {
		if (idx >= operator.length) {
			solve(flag);
			return;
		}

		for (int i = idx; i < operator.length; i++) {
			if (i == 0 || (i - 1 >= 0 && !flag[i - 1])) {
				if (i == operator.length - 1 || (i + 1 < operator.length && !flag[i + 1])) {
					flag[i] = true;
					dfs(flag, idx + 1);
					flag[i] = false;
				}
			}
		}
		dfs(flag, idx + 1);
	}

	public static void solve(boolean[] flag) {
		int[] newArr = num.clone();
		// 괄호 먼저 계산
		for (int i = 0; i < flag.length; i++) {
			if (!flag[i])
				continue;

			int a = num[i];
			int b = num[i + 1];
			char c = operator[i];
			int num = cal(a, b, c);
			newArr[i] = num;
			newArr[i + 1] = num;
		}
		// 괄호 계산 후 순서대로 계산
		for (int i = 0; i < flag.length; i++) {
			if (flag[i])
				newArr[i + 1] = newArr[i];
			else {
				int num = cal(newArr[i], newArr[i + 1], operator[i]);
				newArr[i + 1] = num;
			}

		}
		ans = Math.max(ans, newArr[newArr.length - 1]);
	}

	public static int cal(int a, int b, char c) {
		int result = 0;
		switch (c) {
		case '+':
			result = a + b;
			break;
		case '-':
			result = a - b;
			break;
		case '*':
			result = a * b;
			break;
		}
		return result;
	}
}