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

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

16637번: 괄호 추가하기

 

문제 설명

괄호를 적절하게 추가하여 결과의 최댓값을 출력합니다. 8*3+5를 보면 (8*3)+5, 8*(3+5) 이렇게 2가지 경우가 있습니다. 이때 최댓값은 8*(3+5) = 64입니다.

 

문제에 대한 아이디어

이 문제는 연산자의 우선순위는 존재하지 않습니다. 그러므로 앞에서부터 계산을 하면 됩니다.

문제는 괄호를 어디에 넣어야 할지 선택을 해야 합니다. 괄호는 한 개만 들어갈 수도 있고 여러 개도 들어갈 수 있습니다.

이렇게 괄호를 어디다 넣어야 할 지 기준을 못 정할 때는 브루트포스로 푸는 법이 제일 간단합니다. N의 크기가 19이고 괄호가 들어갈 수 있는 수가 19 / 4로 최대 4개입니다. 그러므로 시간안에 해결할 수 있습니다.

 

괄호를 넣는 법

저는 이런 느낌으로 생각했습니다. 괄호가 들어갈 수 있는 것은 (0, 3) (2, 5), (4, 7), (6, 9) 이렇게 총 4개가 있습니다. 이제 여기서 0개 1개 2개를 뽑아가면서 최대 숫자를 찾기만 하면 됩니다.

 

백트래킹으로 조합

public static void choose(int curNum, int finish, int n, int start){
      if(curNum == finish){
          answer = Math.max(answer, cal(n));
          return;
      }
      for(int i = start; i < pairs.size(); ++i){
          if(arr.size() != 0){ // 바로 앞의 끝보다 시작이 커야 합니다. 괄호는 겹칠 수가 없습니다.
              if(pairs.get(arr.size()-1).e < pairs.get(i).s){
                  arr.add(i);
              }
              else continue;
          }
          else {
              arr.add(i);
          }
          choose(curNum+1, finish, n, i+1);
          arr.remove(arr.size()-1);
      }
  }

 

계산 하는 함수

public static int cal(int n){
      int idx = 0;
      int n_idx = 0;
      Deque<String> dq = new ArrayDeque<>();
      // 괄호를 먼저 넣은 상태에서 계산
      while(n_idx < n){
          int res = 0;
          if(idx < arr.size() && n_idx == pairs.get(arr.get(idx)).s ){
              int num1 = str.charAt(n_idx) - '0';
              int num2 = str.charAt(n_idx+2) - '0';
              res = operation(num1, num2, str.substring(n_idx+1,n_idx+2));
              dq.addLast(String.valueOf(res));
              n_idx += 3;
              idx++;
          }
          else {
              dq.addLast(str.substring(n_idx,n_idx+1));
              n_idx++;
          }
      }
      
      //괄호를 처리한 뒤 숫자 계산
      while(dq.size() != 1){
          int num1 = Integer.parseInt(dq.removeFirst());
          String op = dq.removeFirst();
          int num2 = Integer.parseInt(dq.removeFirst());
          int res = operation(num1,num2,op);
          dq.addFirst(String.valueOf(res));
      }
      
      마지막에 하나 남은 값이 최종 값
      return Integer.parseInt(dq.removeFirst());
}

 

전체 코드

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

public class 백준_16637_괄호_추가하기 {
    public static class Pair{
        int s,e;
        public Pair(int s, int e){
            this.s = s;
            this.e = e;
        }
    }
    static ArrayList<Pair> pairs = new ArrayList<>(); // 가능한 괄호 수
    static ArrayList<Integer> arr = new ArrayList<>(); // 백트래킹 조합
    static String str; // 연산
    static int answer = Integer.MIN_VALUE; // 결과
    public static void main(String[] args) throws IOException {
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(buf.readLine());
        int n = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(buf.readLine());
        str = st.nextToken().toString();
        for(int i = 0; i < n; i+=2){
            if(i+3 <= n){
                pairs.add(new Pair(i, i+3));
            }
        }
        
        for(int i = 1; i < n+1/4; ++i){
            choose(0,i,n, 0);
        }
        
        // 만약 n이 1일 경우 숫자 한개가 답
        if(n == 1) answer = Integer.parseInt(str);
        System.out.println(answer);
    }
    public static int cal(int n){
        int idx = 0;
        int n_idx = 0;
        Deque<String> dq = new ArrayDeque<>();
        while(n_idx < n){
            int res = 0;
            if(idx < arr.size() && n_idx == pairs.get(arr.get(idx)).s ){
                int num1 = str.charAt(n_idx) - '0';
                int num2 = str.charAt(n_idx+2) - '0';
                res = operation(num1, num2, str.substring(n_idx+1,n_idx+2));
                dq.addLast(String.valueOf(res));
                n_idx += 3;
                idx++;
            }
            else {
                dq.addLast(str.substring(n_idx,n_idx+1));
                n_idx++;
            }
        }
        while(dq.size() != 1){
            int num1 = Integer.parseInt(dq.removeFirst());
            String op = dq.removeFirst();
            int num2 = Integer.parseInt(dq.removeFirst());
            int res = operation(num1,num2,op);
            dq.addFirst(String.valueOf(res));
        }
        return Integer.parseInt(dq.removeFirst());
    }
    public static int operation(int num1, int num2, String op){
        if(op.equals("+")){
            return num1 + num2;
        }
        else if(op.equals("-")){
            return num1 - num2;
        }
        else if(op.equals("*")){
            return num1 * num2;
        }
        return 0;
    }
    public static void choose(int curNum, int finish, int n, int start){
        if(curNum == finish){
            answer = Math.max(answer, cal(n));
            return;
        }
        for(int i = start; i < pairs.size(); ++i){
            if(arr.size() != 0){
                if(pairs.get(arr.size()-1).e < pairs.get(i).s){
                    arr.add(i);
                }
                else continue;
            }
            else {
                arr.add(i);
            }
            choose(curNum+1, finish, n, i+1);
            arr.remove(arr.size()-1);
        }
    }
}

https://github.com/SeWooooong/CodingTest_Practice/tree/main/%EB%B0%B1%EC%A4%80/Gold/16637.%E2%80%85%EA%B4%84%ED%98%B8%E2%80%85%EC%B6%94%EA%B0%80%ED%95%98%EA%B8%B0