BOJ_16637_괄호 추가하기

문제 분석

- DFS로 푸는 문제이다.

1) 괄호를 치는 경우

2) 괄호를 안치는 경우

 

 

문제 풀이

 

 

ex)

1) 3+8*7-9*2
2) 3+8*7-(9*2)
3) 3+8*(7-9)*2
4) 3+(8*7)-9*2
5) 3+(8*7)-(9*2)
6) (3+8)*7-9*2
7) (3+8)*7-(9*2)
8) (3+8)*(7-9)*2

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {

	private static int N, max;
	private static ArrayList<Integer> num = new ArrayList<>();
	private static ArrayList<Character> op = new ArrayList<>();

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		String s = br.readLine();
		for (int i = 0; i < N; i++) {
			if (i % 2 == 0)
				num.add(s.charAt(i) - '0');
			else
				op.add(s.charAt(i));
		}
		max = Integer.MIN_VALUE;
		DFS(num.get(0), 0);
		System.out.println(max);
	}// main

	private static void DFS(int hap, int now) { // now는 현재 위치
		if (now >= op.size()) { // 종료 조건
			max = Math.max(max, hap);
			return;
		}

		// 괄호 안치기
		int temp = calc(op.get(now), hap, num.get(now + 1));
		DFS(temp, now + 1); // now+1은 다음 수까지 계산하기

		// 괄호 치기
		if (now + 1 < op.size()) {
			// 오른쪽 값을 먼저 연산함 (괄호를 쳐야하니까)
			int temp2 = calc(op.get(now + 1), num.get(now + 1), num.get(now + 2));
			// 위에서 구한 값과 현재까지의 결과값을 연산함 (앞의 결과 값 + 오른쪽 연산한 결과)
			int temp3 = calc(op.get(now), hap, temp2);
			// 현재까지 결과값을 넘기고 뒤에 괄호를 더 치기위해 +2를 해줌
			DFS(temp3, now + 2);
		}
	}

	private static int calc(int op, int num1, int num2) {
		switch (op) {
		case '+':
			return num1 + num2;
		case '-':
			return num1 - num2;
		case '*':
			return num1 * num2;
		}
		return 0;
	}
}// class-end