[*16637*] 괄호 추가하기 in Java

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

16637번: 괄호 추가하기

---

접근 방식

- 괄호가 아예 없는 경우부터 시작한다.

- 그리고나서 맨끝에서부터 괄호를 채우면서 값을 구해나가는 방식

- 여기서 주의해야할 것은

현재 탐색중인 연산자 배열의 인덱스(opidx)가 맨 끝에 있는 연산자면 

괄호를 추가할 수 없다.

 

아래 그림에서 보면

opidx < 연산자 배열.size()를 만족해야만

괄호를 넣어서 값을 계산할 수 있다.

 

하지만 위 방식을 떠올리지못해서

구글링을 해서 푼 문제 ㅠㅠ

 

주말에 답지 보지 말고 다시 풀어보자!

 

// 괄호가 있는 경우
// 맨 뒤부터 괄호를 묶어준다.
// opidx가 맨 끝이 아닐 경우에만 괄호를 넣어준다.
if (opidx+1<operatorArray.size()) {
    int result2=calculate(numArray.get(opidx+1),numArray.get(opidx+2) , operatorArray.get(opidx+1));
    dfs(opidx+2,calculate(sum, result2, operatorArray.get(opidx)));
}

 

 

 

---

 

 

package day_0810;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
 
public class study16637 {
    static List<Integer> numArray;
    static List<Character> operatorArray;
    static int answer;
    
    public static int calculate(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 opidx, int sum) { // 현재 연산자 인덱스, 직전 재귀 함수에서 계산한 값
        if(opidx==operatorArray.size()) { // 연산자를 모두 사용한 경우
            answer=Math.max(answer, sum); // 최댓값을 구하기 위해 max 함수 사용
            return;
        }
        // 괄호가 없는 경우
        // 정상적으로 앞에서부터 차례대로 계산하는 과정
        int result1=calculate(sum, numArray.get(opidx+1), operatorArray.get(opidx));
        dfs(opidx+1, result1); // 연산자 1개 사용했으니 인덱스 +1 증가, 위에서 계산한 값 넘겨주기
        
        // 괄호가 있는 경우
        // 맨 뒤부터 괄호를 묶어준다.
        // opidx가 맨 끝이 아닐 경우에만 괄호를 넣어준다.
        if (opidx+1<operatorArray.size()) {
            int result2=calculate(numArray.get(opidx+1),numArray.get(opidx+2) , operatorArray.get(opidx+1));
            dfs(opidx+2,calculate(sum, result2, operatorArray.get(opidx)));
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        numArray=new ArrayList<>();
        operatorArray=new ArrayList<>();
        String input=br.readLine();
        
        for(int i=0; i<n; i++) {
            char c = input.charAt(i);
            if (c=='+' || c=='-' || c=='*') {
                operatorArray.add(c);
            }else {
                numArray.add(Character.getNumericValue(c)); // char -> int
            }
        }
        answer=Integer.MIN_VALUE;
        dfs(0,numArray.get(0));
        System.out.println(answer);
    }
 
}