[백준] 16637번 괄호 추가하기

16637번 괄호 추가하기

1. 이해하기

• 왼쪽부터 차례대로 계산한다. 연산자의 우선순위는 괄호만 신경쓴다.
• 괄호를 추가해도 되고 안해도 된다.
• 완전 탐색의 문제이다.

---

2. 구현하기

• solve(index)

  • index를 이용하여 현재 위치에 괄호를 추가하는 방법과 추가하지 않고 넘어가는 방법으로 모든 방법을 살펴보고 그에 따른 값을 계산하였다.

  static int solve(int index) {
          if(index == str.size()) {
              int sum = 0;
              int idx = 0;
              while(idx < str.size()) {
                  if(str.get(idx) == '(') {
                      int cur = 0;
                      int a = str.get(idx+1)-'0';
                      char op = str.get(idx+2);
                      int b = str.get(idx+3)-'0';
                      if(op == '+') {
                          cur = a+b;
                      } else if(op == '-') {
                          cur = a-b;
                      } else if(op == '*') {
                          cur = a*b;
                      }
                      if(idx == 0) {
                          sum = cur;
                      } else {
                          char oper = str.get(idx-1);
                          if(oper == '+') {
                              sum += cur;
                          } else if(oper == '-') {
                              sum -= cur;
                          } else if(oper == '*') {
                              sum *= cur;
                          }
                      }
                      idx += 5;
                  } else if('0' <= str.get(idx) && str.get(idx) <= '9') {
                      if(idx == 0) {
                          sum = str.get(idx)-'0';
                      } else {
                          char op = str.get(idx-1);
                          int cur = str.get(idx)-'0';
                          if(op == '+') {
                              sum += cur;
                          } else if(op == '-') {
                              sum -= cur;
                          } else if(op == '*') {
                              sum *= cur;
                          }
                      }
                      idx++;
                  } else {
                      idx++;
                  }
              }
              return sum;
          }
  
          int ret = MIN;
          for(int i = index; i < str.size(); i++) {
              if('0' <= str.get(i) && str.get(i) <= '9') {
                  if(i+3 <= str.size()) {
                      str.add(i+3,')');
                      str.add(i,'(');
                      int res = solve(i+5);
                      ret = (ret < res) ? res : ret;
                      str.remove(i);
                      str.remove(i+3);
                  }
                  int res = solve(i+1);
                  ret = (ret < res) ? res : ret;
              }
          }
          return ret;
      }

---

3. 전체코드

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static final int MIN = -2100000000;
    static int N;
    static ArrayList<Character> str;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        sc.nextLine();
        String tmp = sc.next();
        str = new ArrayList<>();
        for(int i = 0; i < tmp.length(); i++)
            str.add(tmp.charAt(i));
        System.out.println(solve(0));
    }

    static int solve(int index) {
        if(index == str.size()) {
            int sum = 0;
            int idx = 0;
            while(idx < str.size()) {
                if(str.get(idx) == '(') {
                    int cur = 0;
                    int a = str.get(idx+1)-'0';
                    char op = str.get(idx+2);
                    int b = str.get(idx+3)-'0';
                    if(op == '+') {
                        cur = a+b;
                    } else if(op == '-') {
                        cur = a-b;
                    } else if(op == '*') {
                        cur = a*b;
                    }
                    if(idx == 0) {
                        sum = cur;
                    } else {
                        char oper = str.get(idx-1);
                        if(oper == '+') {
                            sum += cur;
                        } else if(oper == '-') {
                            sum -= cur;
                        } else if(oper == '*') {
                            sum *= cur;
                        }
                    }
                    idx += 5;
                } else if('0' <= str.get(idx) && str.get(idx) <= '9') {
                    if(idx == 0) {
                        sum = str.get(idx)-'0';
                    } else {
                        char op = str.get(idx-1);
                        int cur = str.get(idx)-'0';
                        if(op == '+') {
                            sum += cur;
                        } else if(op == '-') {
                            sum -= cur;
                        } else if(op == '*') {
                            sum *= cur;
                        }
                    }
                    idx++;
                } else {
                    idx++;
                }
            }
            return sum;
        }

        int ret = MIN;
        for(int i = index; i < str.size(); i++) {
            if('0' <= str.get(i) && str.get(i) <= '9') {
                if(i+3 <= str.size()) {
                    str.add(i+3,')');
                    str.add(i,'(');
                    int res = solve(i+5);
                    ret = (ret < res) ? res : ret;
                    str.remove(i);
                    str.remove(i+3);
                }
                int res = solve(i+1);
                ret = (ret < res) ? res : ret;
            }
        }
        return ret;
    }
}

---

4. 느낀점

• 세상은 넓고 잘하는 사람은 많다.
• 고민해서 열심히 짰지만 다른 사람의 코드를 보고 정말 직관적이다 라는 생각이 들었다. 나중에 다시 풀어볼 때 그런 식으로 생각하고 코드를 짤 수 있도록 노력해야겠다.