백준 알고리즘 | 16637 | 괄호 추가하기ㅣJava

출처

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

문제

길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 136이다.

수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 예를 들어, 3+8×7-9×2에 괄호를 3+(8×7)-(9×2)와 같이 추가했으면, 식의 결과는 41이 된다. 하지만, 중첩된 괄호는 사용할 수 없다. 즉, 3+((8×7)-9)×2, 3+((8×7)-(9×2))은 모두 괄호 안에 괄호가 있기 때문에, 올바른 식이 아니다.

수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하는 프로그램을 작성하시오. 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다.

입력

첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다. 연산자는 +, -, * 중 하나이다. 여기서 *는 곱하기 연산을 나타내는 × 연산이다. 항상 올바른 수식만 주어지기 때문에, N은 홀수이다.

출력

첫째 줄에 괄호를 적절히 추가해서 얻을 수 있는 결과의 최댓값을 출력한다. 정답은 2^31보다 작고, -2^31보다 크다.

예시

번호	입력	순서
1	9 3+8*7-9*2	136
2	5 8*3+5	64
3	7 8*3+5+2	66
4	19 1*2+3*4*5-6*7*8*9*0	0
5	19 1*2+3*4*5-6*7*8*9*9	426384
6	19 1-9-1-9-1-9-1-9-1-9	24

풀이

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class BOJ16637
{
	static int ans; // 최댓값
	static int n;
	
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		n = Integer.parseInt(br.readLine());
		String s = br.readLine();
		
		LinkedList<Node> origin = new LinkedList<Node>(); //LinkedList()<String>이 아닌 LinkedList<String>()로
		
		for(int i=0;i<n;i++)
		{
			char temp=s.charAt(i);
			Node node;
			if(temp=='+'||temp=='-'||temp=='*')
			{
				node = new Node(temp-'A');
/*				System.out.println(temp+" "+(temp-'A'));
				+ -22
				* -23
				- -20
*/
			}
			else node = new Node(temp-'0');
			origin.add(node);
		}
		
		for(int i=0;i<n/2;i++)
		{
			dfs(i,origin);
		}
		System.out.println(ans);
	}
	
	static class Node
	{
		int node;
		Node(int node)
		{
			this.node=node;
		}
	}
	
	static void dfs(int di,LinkedList <Node>dList)
	{
		if(dList.size()==1)
		{
			Node temp = dList.poll();
			ans=Math.max(ans,temp.node);
			return;
		}
		
		int index=(di+1)*2-1;				// 계산할 연산자가 위치한 인덱스값
		Node op=dList.get(index);		// 연산자의 종류
		Node left=dList.get(index-1);	// 연산자 왼쪽에 위치한 숫자
		Node right=dList.get(index+1);	// 연산잔 오른쪽에 위취한 숫자
		
		int result;						// 연산 결과값
		
		if(op.node=='+'-'A')
		{
			result=left.node+right.node;
		}
		else if(op.node=='-'-'A')
		{
			result=left.node-right.node;
		}
		else
		{
			result=left.node*right.node;
		}
		
		//System.out.println(left.node+" "+(op.node+'A')+" "+right.node+" = "+result+"\n");
		
		Node temp = new Node(result);
		dList.add(index+1,temp);
		dList.remove(index-1);
		dList.remove(index-1);
		dList.remove(index-1);
		
		for(int i=0;i<dList.size()/2;i++)
		{
			dfs(i,dList);
		}
		
		
	}
}