백준 16637번 괄호 추가하기

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

public class AddBracket {
    static int N;
    static String str;
    static int[] nums;
    static int len;
    static char[] op;
    static int answer = Integer.MIN_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        str = br.readLine();
        len = str.length();
        nums = new int[len/2+1];
        op = new char[len/2];

        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if(c=='+'||c=='-'||c=='*'){
                op[i/2] = c;
                continue;
            }
            nums[i/2] = c-'0';
        }
        dfs(nums[0],0);
        System.out.println(answer);

    }
    public static int cal(int a, int b, char c){
        if(c=='+'){
            return a+b;
        }else if(c=='-'){
            return a-b;
        }else if(c=='*'){
            return a*b;
        }
        return -1;
    }
    public static void dfs(int result,int index){
        if(index>=len/2){
            answer = Math.max(answer,result);
            return;
        }
        int res = cal(result,nums[index+1],op[index]);
        dfs(res,index+1);
        if(index<len/2-1){
            int res2 = cal(result,cal(nums[index+1],nums[index+2],op[index+1]),op[index]);
            dfs(res2,index+2);
        }

    }
}

풀이방법

전체적인 설계는 우선, 처음부터 순차적으로 연산한 후, 끝지점에 도달하면, 다시 백트래킹하면서 괄호를 씌워준다. 이때, 괄호를 씌운 후 다시 dfs에 넣어준다.
코드로 살펴보면

public static void dfs(){
	if(){// 끝지점 도달시 최댓값

	}
    res1 = // 해당인덱스부터 순차적으로 계산
    dfs();
    res2 = // 괄호를 씌워서 계산
    dfs();
}

이러한 구조가 된다.

즉, 한 dfs싸이클에서
1. 해당 숫자를 순차적으로 계산 후 dfs()에 재귀.
2. 해당 숫자를 괄호로 묶은 뒤 계산 후 dfs()에 재귀.
이렇게 두번 진행하는 것이다.

👉이때, 괄호로 묶는 부분이 조금 복잡한데, 다음 숫자와, 다다음 숫자를 괄호로 묶어서 연산하고, 그 값을 현재까지의 결과값과 다시 연산해준다.
cal(result,cal()) 이런 구조가 되는 셈이다.

📢이때 이값을 dfs에 넣어주는데, 다다음 숫자까지 이미 괄호로 묶어서 계산했으므로, dfs에 index+1 이 아닌, index+2를 해준다.

이후, 끝지점에 도달하면 max값을 구해준다.(음수가 최대값일 수 있으므로, max초깃값 0으로 하면 안됨!)

후기

처음에 그리디 방식으로 살펴보다가, 변수가 너무 많고, 입력값도 작아 충분히 완탐이 될것 같아서 백트래킹까지는 떠올렸다.
근데 뭔가 괄호가 여러개 있을때는, 백트래킹 처리를 어떻게 해야할지 몰라서 설계를 못했다.
하지만 이문제는 { 이전값 + 현재숫자 or 괄호} 이구조로 dfs가 진행되기때문에 돌면서 괄호가 여러개 자연스레 나와서 고려할 필요가 없었다.
거의 다 왔는데, 힌트를 보고 풀어서 아쉽다.