[BOJ 16637] 괄호 추가하기 (Java)

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

16637번: 괄호 추가하기

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

public class Main_BOJ_16637 {
	static int N;
	static String s;
	static int[] nums;
	static char[] op;
	static int max=Integer.MIN_VALUE;
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		N=Integer.parseInt(br.readLine());
		s=br.readLine();
		nums=new int[N/2+2];
		op=new char[N/2+1];
		int ncnt=0, ocnt=0;
		nums[ncnt++]=0;
		op[ocnt++]='+';
		for (int i=0; i<N; i++) {
			if (s.charAt(i)>='0' && s.charAt(i)<='9') nums[ncnt++]=s.charAt(i)-'0';
			else op[ocnt++]=s.charAt(i);
		}
		dfs(1,0);
		System.out.println(max);
	}
	private static void dfs(int idx, int sum) {
		if (idx==N/2+2) {
			max=Math.max(max, sum);
			return;
		}
		dfs(idx+1, calc(sum, nums[idx], op[idx-1]));
		if (idx<N/2+1) {		//괄호 o
			int tot=calc(nums[idx], nums[idx+1], op[idx]);
			dfs(idx+2, calc(sum, tot, op[idx-1]));
		}
		
	}
	
	private static int calc(int a, int b, char op) {
		switch(op) {
		case '+':
			return a+b;
		case '-':
			return a-b;
		case '*':
			return a*b;
		}
		return 0;
	}

}

 

DFS 문제이다. 조금 까다로웠다. 괄호 묶는 경우 / 안 묶는 경우로 나뉘어서 DFS 를 돌려주는게 포인트다.

한 idx를 기준점 삼아, 그 바로 오른쪽 옆의 숫자와 묶을 건지 (괄호를 칠건지) / 아니면 이전 결과값과 함께 묶을건지 (괄호 치지 않고 연산) 해서 대상 idx를 이동시켜줘야 한다.