자바(백준) 16637 괄호 추가하기

오답 노트 & 새로 알게 된 점

백트래킹으로 풀어야지 라는 생각을 했지만 구현을 하지 못했다.

구글의 힘을 빌려서 문제를 해결했다,,

 

처음에 수식의 길이가 N개라고 하여, 숫자는 결국 N / 2 + 1개가 있게 되고, 거기서 -1을 하면 괄호로 묶을 수 있는 수들의 경우의 수가 된다.

이걸 이용해서 순서, 중복 X인 조합을 구하여 계산하려 했지만 하지 못했다.

 

 

다른 풀이에서는 백트래킹을 이용한다.

 

뒤에 괄호가 있다고 생각 or 뒤에 괄호가 없다고 생각한다.

뒤에 괄호가 있다면 현재 idx에서 다음 idx+1, idx+2의 계산한 값과 현재 idx값을 계산해야한다.

 

그래서 예제 1번을 디버깅 하여 어떻게 계산이 이뤄지는지 손으로 작성해보았다.

---

코드

import java.io.*;
import java.util.*;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N, ans = Integer.MIN_VALUE;
    static int A[];
    static char op[];
    public static void main(String[] args) throws IOException {
        input();
        pro();
    }
 
    static void pro() {
        dfs(A[0], 0);
 
        System.out.println(ans);
    }
 
    static void dfs(int val, int idx) {
        if(idx >= op.length){
            ans = Math.max(ans, val);
            return;
        }
 
        //괄호 없을 때 앞에서부터 계산
        int rel1 = calcul(val, A[idx+1], op[idx]);
        dfs(rel1, idx + 1);
 
        //괄호 있다고 생각
        if (idx + 1 < op.length) {
            int rel2 = calcul(A[idx + 1], A[idx + 2], op[idx + 1]);
 
            dfs(calcul(val, rel2, op[idx]), idx + 2);
        }
    }
 
    static int calcul(int num1, int num2, char op) {
        if(op == '+') return num1 + num2;
        else if(op == '-') return num1 - num2;
        return num1 * num2;
    }
 
    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        N = atoi(br.readLine());
 
        A = new int[N / 2 + 1];
        op = new char[N / 2];
 
        String str = br.readLine();
        int idx1 = 0;
        int idx2 = 0;
        for (int i = 0; i < N; i++) {
            char ch = str.charAt(i);
 
            if(i % 2 == 0) A[idx1++] = ch - '0';
            else op[idx2++] = ch;
        }
    }
}