백준_16637_괄호 추가하기

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

 

이번 문제는 수 사이에 괄호를 적절히 추가하여 식의 결과 값을 최대로 만드는 것이다.

 

주의해야 할 점은 괄호 안에 괄호를 추가할 수 없다는 것이다 예를 들어 (3 * 2) + (2 + 4 )는 되지만

 

(3 * 5 - ( 2 + 7 )) 과 같은 경우는 + 연산자가 총 두 쌍의 괄호로 감싸 져 있기 때문에 안된다.

 

여기서 알 수 있는 점이 있다! 한 연산자가 괄호로 감싸이면 다음 연산자는 절대로 괄호가 씔 수 없다.

어떠한 연산자에 괄호가 씌면 양옆 연산자는 괄호가 씔 수 없다.

 

 

예를 들어보자 (문제 조건에서 수식은 괄호를 제외하고는 왼쪽에서 오른쪽으로 진행된다.)

 

2 * 4 + 4 - 2라는 식이 있을 때  

 

( 1 ) 현재 식에서 괄호를 씌우고 다음으로 진행하는 경우  

(2 * 4) + 4  - 2 => 8 + 4 - 2 가된다 => 이후에 이식에서 ( 1 ) 적용하거나 ( 2 ) 적용해나가면서 풀면 된다 

결국에 재귀로 해결하면 되는 것이다. 계속 적용해보자 

( 1 ) 적용 시 : (8 + 4 ) - 2 => 12 - 2 가 된다 이후 연산자가 하나뿐이기 때문에 10 이 최종 값

( 2 ) 적용 시 : 2 * (8 - 2) => 12 가 된다 이후 연산자가 없기 때문에 12 가 최종 값 

 

( 2 ) 현재 식에서 씌우지 않고 다음 식에서 씌우는 경우

2 * (4 + 4) - 2  => 16 - 2 가 된다  이후 연산자가 하나뿐이기 때문에 14 가 최종 값

 

다음은 전체 코드이다.

import java.util.Scanner;

public class Bj_16637 {
	 static char[] op;
	 static int[] num;
	 static String st;
	 static int n;
	 static int ans = Integer.MIN_VALUE;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		st = sc.next();
		op = new char[(n / 2)];
		num = new int[(n / 2) + 1];
        // 주어진 식을 숫자부분과 연산자 부분으로 나눈다.
		for(int i = 0; i < n; i++) {
			if(i % 2 == 0) {
				num[i / 2] =Integer.parseInt(st.charAt(i) + "");
			}else {
				op[i / 2] = st.charAt(i);
			}
		}
		
		operation(0, num[0]);
		System.out.println(ans);
		}
	
	static void operation(int index, int value) {
    // 더이상 계산하기 위한 연산자가 없음 / 종료 조건
		if(index >= op.length) {
			ans = ans < value ? value : ans;
			return;
		}
        // 위에 설명한 ( 1 ) 번 적용한경우 
		int temp = value;
		value = calc(op[index], value, num[index + 1]);
		operation(index + 1, value);
		
        // 위에 설명한 ( 2 ) 번 적용한경우 
		if(index + 1 < op.length) {
			temp = calc(op[index], temp, calc(op[index + 1], num[index + 1], num[index + 2]));
			operation(index + 2, temp);
		}
	}
	
    // 계산을 편리하게 하기위해 만들었다.
	static int calc(char op, int num1, int num2) {
		switch (op) {
			case '+':
				return num1 + num2;
			case '-':
				return num1 - num2;
			case '*':
				return num1 * num2;
		}
		return 0;
	}
	}