BOJ. 16637번. 괄호 추가하기

 

  이 문제를 처음에 접근할 때, 하나의 배열로 인덱스를 모두 관리하려고 했었는데 그게 쉽지 않았다. 따라서 number와 operation에 대한 배열 두개로 나눠서 풀었는데 훨씬 인덱스 관리가 편리해졌다.

1. 기본적인 아이디어는 dfs이다
2. 각 재귀호출 시 마다, operation의 인덱스를 하나씩 키워가면서 계산한다.
3. 이때 계산은 괄호를 추가하는 경우, 추가하지 않는 경우로 나누며
    3-1. 괄호 추가하는 않는(필요없는) 경우 : 그대로 연산한 결과를 다음 연산자에게 넘겨준다.
    3-2. 괄호 추가하는 경우: 다음연산자를 먼저 계산하고, 다다음 연산자에게 넘겨준다.

 

www.acmicpc.net/problem/16637

16637번: 괄호 추가하기

 

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

public class Main {


	static long ans=Long.MIN_VALUE,len;
	static ArrayList<Character> nums = new ArrayList<Character>();
	static ArrayList<Character> ops = new ArrayList<Character>();
	
	private static long calculate(long a, char op, long b) {
		if(op == '+') {
			return a+b;
		}else if(op == '-') {
			return a-b;
		}else {
			return a*b;
		}
	}
	
	private static void solution(long idx, long result) {
		if(idx>=ops.size()) {
			ans = Math.max(ans, result);
			return;
		}
//		괄호 없는 경우
		solution(idx+1, calculate(result,ops.get((int) idx),nums.get((int) (idx+1))-'0'));
		
//		괄호 넣는 경우
		if(idx+1<ops.size()) {
			long tmp = calculate(nums.get((int) (idx+1))-'0', ops.get((int) (idx+1)), nums.get((int) (idx+2))-'0');
			solution(idx+2, calculate(result, ops.get((int) idx) ,tmp));
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		len = Integer.parseInt(br.readLine());
		String s = br.readLine();
		
		for(int i=0; i<len; i++) {
			if((int)s.charAt(i)>=48 && (int)s.charAt(i)<=57) {
				nums.add(s.charAt(i));
			}else {
				ops.add(s.charAt(i));
			}
		}
		solution(0,nums.get(0)-'0');
		System.out.println(ans);
	}

}