[BOJ - JAVA] 21943 - 연산 최대로(브루트포스)

# 주소

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

21943번: 연산 최대로

# 문제

# 문제 해설 및 코드 리뷰

import java.lang.reflect.Array;
import java.util.*;

class Main {
    static int n,a,b;
    static int[] arr;
    static int[] ans;
    static boolean[] visit;
    static ArrayList<Integer> list = new ArrayList<>();
    static int max = Integer.MIN_VALUE;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        arr = new int[n];
        ans = new int[n];
        visit = new boolean[n];
        for(int i = 0; i < n; i++)
            arr[i] = scan.nextInt();
        a = scan.nextInt();
        b = scan.nextInt();
        dfs(0,0,0);
        System.out.println(max);
    }
    static void dfs(int x, int p, int q){
        if(p <= a && q <= b){
            if(x == n){
                max = Math.max(max, calc());
                return;
            }
        }
        for(int i = 0; i < n; i++){
            if(!visit[i]){
                visit[i] = true;
                list.add(arr[i]);
                if(x == 0)
                    dfs(x + 1, p, q);
                else{
                    ans[x] = 1;
                    dfs(x + 1, p + 1, q);
                    ans[x] = 2;
                    dfs(x + 1, p, q + 1);
                    ans[x] = 0;
                }
                list.remove(x);
                visit[i] = false;
            }
        }
    }
    static int calc(){
        ArrayList<Integer> temp_list = new ArrayList<>();
        int temp = list.get(0);
        for(int i = 1; i < n; i++){
            if(ans[i] == 1)
                temp += list.get(i);
            if(ans[i] == 2) {
                temp_list.add(temp);
                temp = list.get(i);
            }
        }
        temp_list.add(temp);
        temp = 1;
        for(int i = 0; i < temp_list.size(); i++)
            temp *= temp_list.get(i);
        return temp;
    }
}

백트래킹 + 브루트포스 문제입니다.

같이 살펴봅시다.

Scanner scan = new Scanner(System.in);
n = scan.nextInt();
arr = new int[n];
ans = new int[n];
visit = new boolean[n];

Scanner를 이용하여 입력받았습니다.

그리고 n을 입력받고 arr는 숫자들의 배열, ans는 '+', 'x'의 배열로 사용하겠습니다.

visit배열도 필요합니다. 백트래킹하는데 있어서 방문한 인덱스와 아닌 곳을 구분하기 위해서 필요합니다.

for(int i = 0; i < n; i++)
    arr[i] = scan.nextInt();
a = scan.nextInt();
b = scan.nextInt();
dfs(0,0,0);

n의 크기만큼 arr를 입력받겠습니다.

그리고 '+'의 개수를 a, 'x'의 개수를 b에 담고 dfs(0,0,0);을 실행합니다.

dfs의 파라미터로는 다음과 같습니다.

static void dfs(int x, int p, int q){
    if(p <= a && q <= b){
        if(x == n){
            max = Math.max(max, calc());
            return;
        }
    }

x는 index 크기입니다. 시행 횟수가 n번 되었을 떄 max에 calc()와 기존의 max를 비교하여 갱신할 것입니다.

이 x가 n만큼 채우기 위해선 재귀를 해야겠죠???

for문을 이용하여 n까지 탐색합시다.

for(int i = 0; i < n; i++){
    if(!visit[i]){
        visit[i] = true;
        list.add(arr[i]);

그리고 방문하지 않은 !visit값에 대해서만 탐색을 진행할 것입니다.

이렇게 하면 수학에서 '같은 것이 있는 순열'의 패턴으로 경우의 수를 만들 수 있게됩니다.

그리고 visit 은 true로 잠시 바꾸고

list에는 arr를 추가합니다.

if(x == 0)
    dfs(x + 1, p, q);
else{
    ans[x] = 1;
    dfs(x + 1, p + 1, q);
    ans[x] = 2;
    dfs(x + 1, p, q + 1);
    ans[x] = 0;
}

그런데 처음 시작하자마자 연산부터 담으면 안되기 때문에 x가 0일 때는 그냥 dfs에 (x +1)을 하여 재귀로 보냅니다.

그런다음 x가 0이 아닐 때 즉, arr가 list에 담겨 있고 연산을 수행가능할 때에 else문을 실행합니다.

else문은 재귀를 2가지로 분류할 수 있겠습니다.

ans[x] = 1일 때에는 '+'덧셈을 의미합니다.

이 때에는 dfs(x + 1, p + 1, q)를 실행합니다.

ans[x] = 2일 때에는 'x' 곱셈을 실행할 것입니다.

곰셈이기 때문에 dfs(x + 1, p , q + 1)을 실행할 것입니다.

다 끝나고 나서 ans를 초기화해야하는데 ans[x] = 0으로 바꿉니다.

이 모든 것이 인덱스가 1번씩 증가할 때마다 이 중에 한가지가 일어나게 될 것입니다.

그리고 한 가지의 경우에 대해 다 조합을 다 짰으면 list에서 값을 제거하고 visit도 false로 만들어 백트래킹을 끝냅니다.

이후 이렇게 갖고온 ans와 list로 calc()를 해볼게요.

static int calc(){
    ArrayList<Integer> temp_list = new ArrayList<>();
    int temp = list.get(0);
    for(int i = 1; i < n; i++){
        if(ans[i] == 1)
            temp += list.get(i);
        if(ans[i] == 2) {
            temp_list.add(temp);
            temp = list.get(i);
        }
    }
    temp_list.add(temp);
    temp = 1;
    for(int i = 0; i < temp_list.size(); i++)
        temp *= temp_list.get(i);
    return temp;
}

calc()함수는 다음과 같습니다.

temp_list라는 ArrayList<>를 이용해보겠습니다.

temp들을 담을 자료구조입니다.

temp는 list.get(0)을 하여 제일 첫 번째 값을 가져왔습니다.

당연히 첫 번째 인덱스는 저장했으므로 for문은 1부터 n까지 탐색합니다.

ans[i] = 1일 때에는 덧셈을 의미하므로 우선순위가 따로 존재하지 않습니다.

그렇기에 temp에 계속해서 list.get(i)를 더해줍니다.

그러나 ans[i] = 2일 때에는 temp_list.add(temp)하여 temp_list에 temp들을 담을 것입니다.

이 때 이 연산 이후 temp에는 list.get(i)를 하여 리셋합니다.

이 과정을 통해, temp는 덧셈이 진행된 temp값들. 그리고 temp_list에는 덧셈이 진행되었던 temp들을 모두 담아두게 되겠지요.

마지막 list값도 temp_list에 넣으면 마무리됩니다.

그리고 temp는 1로 다시 초기화 한다음 temp에 temp_list의 값들을 모두 곱해주면 temp가 되는데요.

이 원리가 이해 안된다면 이렇게 생각을 해봅시다.

문제에서 +와 x가 우선순위가 같다고 했습니다.

그렇기에 +또는 x가 랜덤으로 백트래킹을 이용하여 수많은 경우의 수로 조합될 것입니다.

그리고 문제에서 정수의 순서를 바꾸어도 상관없다고 되어 있었으므로 더더욱 백트래킹이 필요하게 됩니다.

모든 경우의 수에 대한 탐색이 가능하기 때문이에요.

그래서 브루트포스에는 백트래킹과 재귀를 빼놓을래야 빼놓을 수 없는 관계인 것 같습니다.

괄호를 염두해야 하는것 아니냐 할 수 있으실 것 같은데, 백트래킹은 모든 탐색가능한 영역을 조합할 수 있습니다.

따라서 괄호가 아애 없는 것부터 시작해서 꽉채운 것까지 모두 표현 가능하다고 말씀드리고 싶습니다.

감사합니다.