[백준 알고리즘] 16637번 : 괄호 추가하기 (JAVA) 문제 풀이

문제

길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 136이다.

수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 예를 들어, 3+8×7-9×2에 괄호를 3+(8×7)-(9×2)와 같이 추가했으면, 식의 결과는 41이 된다. 하지만, 중첩된 괄호는 사용할 수 없다. 즉, 3+((8×7)-9)×2, 3+((8×7)-(9×2))은 모두 괄호 안에 괄호가 있기 때문에, 올바른 식이 아니다.

수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하는 프로그램을 작성하시오. 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다.

입력

첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다. 연산자는 +, -, * 중 하나이다. 여기서 *는 곱하기 연산을 나타내는 × 연산이다. 항상 올바른 수식만 주어지기 때문에, N은 홀수이다.

출력

첫째 줄에 괄호를 적절히 추가해서 얻을 수 있는 결과의 최댓값을 출력한다. 정답은 231보다 작고, -231보다 크다.

 

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

16637번: 괄호 추가하기

어떻게 풀 것인가?

골드5에 랭크된 어려운 문제였다.

DFS를 이용하여 풀었는데 숫자와 연산자를 리스트에 따로 다은 이후 처리를 해준다.

단, 인덱스가 홀수일때는 연산자, 짝수일때는 숫자가 들어온다.

 

풀면서 놓쳤던점

괄호라는 단어만 보고 스택에 너무 꽂혀서 그런지 DFS라는 점을 고려하지않고 풀었던 것 같다.

 

이 문제를 통해 얻어갈 것

DFS에 대해서 다시금 공부할 수 있었다.

 

내 코드 

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

public class Main {
    static int n;
    static int max = Integer.MIN_VALUE;
    static ArrayList<Integer>num = new ArrayList<>();
    static ArrayList<Character> op = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

         n = Integer.parseInt(br.readLine());
         
         String t = br.readLine();
         for(int i=0; i<n; i++) {
             if(i%2==0) {
                 num.add(t.charAt(i)-'0');
             }
             else {
                 op.add(t.charAt(i));
             }
         }
         int start = num.get(0);
         dfs(0,start);
         System.out.println(max);
    }
    public static void dfs(int now, int sum) {
        if(now>=op.size()) {
            max = Math.max(max, sum);
            return;
        }
        // 1. 괄호 안치고 진행하기
        int one = cal(now, sum, num.get(now+1));
        dfs(now+1, one);
        // 2. 괄호 치고 진행하기
        if(now+1 < op.size()) { // 인덱스 범위 오류를 제거하기 위해
            int two = cal (now+1, num.get(now+1), num.get(now+2));
            int result = cal (now, sum, two);
            dfs(now+2, result);
        }
   }
    public static int cal(int op_idx,int a, int b) {
        switch(op.get(op_idx)) {
        case '+':
            return a+b;
        case '-':
            return a-b;
        case '*':
            return a*b;
        }
        return 1;
    }
}