[백준] 괄호 추가하기 16637 java - dfs

 

괄호가 없는 경우/있는 경우를 모두 고려해서 완전탐색으로 풀이하면 된다

dfs를 생각하지 못해서 삽질하다가 다시 풀었다 ㅜㅜ

두 가지 경우로 나뉘기 때문에 dfs를 이용해서 괄호가 없는 경우를 먼저 모두 구한 후

있는 경우를 구하면 쉽게 풀 수 있다

 

 

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

 

 

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

public class Main {
    static int N;
    static int answer = Integer.MIN_VALUE;
    static ArrayList<Integer> nums;
    static ArrayList<Character> operator;
    static void dfs(int depth, int result){
        //System.out.println("depth="+depth+" result="+result);
        //연산 종료 시점
        if(depth == N/2){
            answer = Math.max(answer, result);
            return;
        }

        //괄호가 없는 경우
        int cal = calculate(result, nums.get(depth+1), operator.get(depth));
        dfs(depth+1, cal);

        //괄호가 있는 경우
        if(depth+2<=N/2){
            cal = calculate(result, calculate(nums.get(depth+1), nums.get(depth+2),operator.get(depth+1)), operator.get(depth));
            dfs(depth+2, cal);
        }

    }
    static int calculate(int n1, int n2, char operator){
        if(operator=='*')
            return n1*n2;
        else if(operator=='+')
            return n1+n2;
        else
            return n1-n2;
    }
    public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

            N = Integer.parseInt(br.readLine());
            String arr = br.readLine();

            nums = new ArrayList<>();
            operator = new ArrayList<>();

            for(int i=0;i<N;i++){
                if(i%2==0)
                    nums.add(arr.charAt(i)-'0');
                else
                    operator.add(arr.charAt(i));
            }
            dfs(0, nums.get(0));

            System.out.println(answer);

    }
}