BOJ - 괄호 추가하기 16637번 (JAVA)

❓ 문제 - 백준 괄호 추가하기 16637번 - JAVA 풀이법

 

출처 

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

16637번: 괄호 추가하기

 

 

📝 문제해결법

1. 이 문제는 DFS(백트래킹)으로 구현하였다.

• DFS 내에서는 괄호를 안치고 계산한 경우와, 괄호를 치고 경우 이렇게 두 개를 가지치기를 하면서 푼다.
• 예를 들어 

3+8*7-9*2 에서

3+8*7 ~~ 로 오른쪽에 괄호를 안 치고 계산하는 경우
3+(8*7) ~~ 로 오른쪽에 괄호를 치고 계산하는 경우

2. 느낀점

• 코드는 간결한데 로직 생각하기 빡세서 구글링 했다...
• 조만간 백트래킹 내 좋은 문제들로 풀어야겠다...!

 

 

 

💻 소스코드

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


public class Main_16637 {
    public static int n;

    public static ArrayList<Integer> number;
    public static ArrayList<Character> cal;

    public static int ans;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        char[]input = br.readLine().toCharArray();

        cal = new ArrayList<>();
        number = new ArrayList<>();
        for(int i=0;i<n;i++){
            if(input[i] == '*' || input[i] == '+' || input[i] == '-'){
                cal.add(input[i]);
            } else {
                number.add(input[i] - '0');
            }
        }
        ans = Integer.MIN_VALUE;
        dfs(number.get(0), 0);




        System.out.println(ans);
    }

    public static void dfs(int result, int idx){
       if(idx == cal.size()){
           ans = Math.max(ans, result);
           return;
       }
       // 괄호를 안치고 지나가기
       dfs(cal(result, number.get(idx+1), cal.get(idx)), idx+1);
       // 괄호를 치고 지나가기
       if(idx+2 <= cal.size()){
           dfs(cal(result, cal(number.get(idx+1), number.get(idx+2),cal.get(idx+1)), cal.get(idx)),idx+2);

       }
    }



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