[BOJ - JAVA] 16637 - 괄호 추가하기 (브루트포스)

# 주소

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

16637번: 괄호 추가하기

# 문제

# 문제 해설 및 코드 리뷰

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

class Main{
    static int n,num,str;
    static int[] arr;
    static int[] ans;
    static Long max = Long.MIN_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        num = (n / 2) + 1; str = (n / 2); //num = 5, str = 4
        arr = new int[num];
        ans = new int[str];
        String s = br.readLine();
        for(int i = 0; i < num; i++){
            arr[i] = s.charAt(2 * i) - '0';
        }
        for(int i = 0; i < str; i++){
            char c = s.charAt(i * 2 + 1);
            if(c == '+')
                ans[i] = 1;
            else if(c == '*')
                ans[i] = 2;
            else if(c == '-')
                ans[i] = 3;
        }
        // arr = 3 8 7 9 2 ans = + * - (1 2 3)
        for(int i = 0; i < str; i++){
            dfs(i);
        }
        System.out.println(max);
    }
    static void dfs(int index) {
        int sum = 0;
        if (ans[index] == 1) {
            sum += arr[index] + arr[index + 1];
        } else if (ans[index] == 2) {
            sum += arr[index] * arr[index + 1];
        } else
            sum += arr[index] - arr[index + 1];
        //9
        //3+  8*7(1,2 1)  -9*2
        ArrayList<Integer> list = new ArrayList<>();
        ArrayList<Integer> list2 = new ArrayList<>();
        for (int i = 0; i < num; i++) {
            if(i == index){
                list.add(sum);
                continue;
            }
            if(i == index + 1)
                continue;
            list.add(arr[i]);
        }
        for(int i = 0; i < str; i++){
            if(i == index)
                continue;
            list2.add(ans[i]);
        }
        max = Math.max(max, search(list, list2));
    }
    static int search(ArrayList<Integer> list, ArrayList<Integer> list2) {
        int sum = list.get(0);
        for(int i = 0; i < list2.size(); i++){
            if(list2.get(i) == 1){
                sum = sum + list.get(i +1);
            }else if(list2.get(i) == 2){
                sum = sum * list.get(i + 1);
            }else if(list2.get(i) == 3){
                sum = sum - list.get(i + 1);
            }
        }
        return sum;
    }
}

진짜 기가막히게 풀었다 싶었는데 이거 괄호를 여러 개 추가할 수 있는 문제더라고요.

전 딱 한 번만 추가되는줄 알고 열심히 1시간동안 풀어서 제출했는데 하긴 골드2 문제가 이렇게 간단히 풀릴리없죠 ㅠㅠ

다시 코드를 짜봐야겠습니다.

괄호를 여러개 넣는데 모든 경우의 수를 따져보려면 어떻게 해야할까요?

백트래킹을 이용해야할 것 같죠?

그러므로 지금 시각이 새벽 2시 49분이니까 넘 늦어서 내일 다시 포스팅해서 올리겠습니다.

감사합니다.

괄호 한 개만 추가해야 한다면 위에처럼 풀면 됩니다.

아 이 이후 2시간 동안 진짜 열심히 쓴 글이 있는데 뒤로가기 잘못 눌러서 싹다 뒷내용이 지워졌네요.

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

class Main {
    static int n;
    static ArrayList<Integer> list = new ArrayList<>();
    static ArrayList<Character> list2 = new ArrayList<>();
    static Long max = Long.MIN_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        String str = br.readLine();
        for (int i = 0; i < n / 2 + 1; i++) {
            list.add(str.charAt(i * 2) - '0');
        }
        for (int i = 0; i < n / 2; i++)
            list2.add(str.charAt(i * 2 + 1));
        dfs(0, list.get(0));
        System.out.println(max);
    }
    static void dfs(int cnt, int sum) {
        if(cnt >= list2.size()){
            max = Math.max(max, sum);
            return;
        }
        int x = calc(list2.get(cnt), sum, list.get(cnt + 1));
        dfs(cnt + 1, x);
        if(cnt + 1 < list2.size()){
            int y = calc(list2.get(cnt + 1), list.get(cnt + 1), list.get(cnt + 2));
            dfs(cnt +2, calc(list2.get(cnt), sum, y));
        }
    }
    static int calc(Character s, int sum, int y){
        if(s == '+')
            return sum + y;
        else if(s == '*')
            return sum * y;
        else if(s == '-')
            return sum - y;
        return 1;
    }
}

하.. ㅠㅠㅠ 한 번 더는 못쓰겠네요.. 

궁금하신거 있으시면 댓글 남겨주세요 바로 답변드리게씁니다. ㅠㅠㅠ