[JAVA] 괄호 추가하기 (백준 16637)

아직까지 문자하나하나 다루는 거랑 알고리즘 할때, 컬렉션을 다루는 스킬이 많이 부족함을 느낀다.

 

매일 하나씩 풀다보면 적응 되겠지...

 

 

dfs로 간단하게 풀수있다.

 

a + b - c 가 있다면

 

1) a+b 하고 넘기기

2) a+ (b-c) 하고 넘기기

 

그림으로 설명하면 아래와 같다.

 

<코드>

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

public class Main {

    static int n;
    static int answer = -(int)Math.pow(2,31);
    static ArrayList<Integer> nums = new ArrayList<>();
    static ArrayList<Character> ops = new ArrayList<>();

    public static int cal(int a,int b,char op){
        if(op=='+') return a+b;
        else if(op=='-') return a-b;
        else return a*b;
    }

    public static void dfs(int idx,int curSum){
        if(idx==ops.size()){
            answer = Math.max(answer,curSum);
        }
        else{
            dfs(idx+1,cal(curSum,nums.get(idx+1),ops.get(idx)));
            if(idx+2 <=ops.size())
            dfs(idx+2,cal(curSum,cal(nums.get(idx+1),nums.get(idx+2),ops.get(idx+1)),ops.get(idx)));
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader( new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter( new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        for(char c : br.readLine().toCharArray()){
            if(c>='0' && c<='9') nums.add(Character.getNumericValue(c));
            else ops.add(c);
        }

        dfs(0,nums.get(0));
        bw.write(Integer.toString(answer)+'\n');

        br.close();
        bw.flush();
        bw.close();
    }
}