[14888] 연산자 끼워넣기

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

---

수열 사이사이에 주어진 연산자를 모두 끼워넣어서 계산하여 최댓값과 최솟값을 구하는 브루트 포스 문제입니다. 다른 시뮬레이션이나 DFS, BFS, DP 문제도 풀어야하는데 브루트포스만 풀어서 큰일났습니다........ 이번 문제가 제가 풀었던 다른 브루트 포스 문제와 다른 점은 다른 문제들은 조합을 이용하여 완전 탐색을 진행했는데, 이번엔 순열을 이용하는 점이 달랐습니다. 브루트 포스 문제는 많이 나오는데 조합과 순열, 재귀에 대해 완벽한 이해가 중요하다고 생각했습니다.

그래서 재귀로 순열을 출력하는 방법을 먼저 공부하고 문제를 해결했습니다. 더 간단하게 풀 수도 있을 것 같은데, 풀다보니 코드가 엄청 조잡한것 같습니다.....ㅋ 정답을 보고풀면 깔끔해지는데 정답을 안보고 푸니까 코드가 지저분해지는것 같습니다. 일단 푸는게 중요하니까 깔끔한 코드로 정리는 나중에하고 제가 푼 방법에 대해서 설명해 보겠습니다.

< 문제 풀이 >

1. 수열은 배열 A[] 에 입력받고, op[] 배열에 연산자 4개를 입력받았습니다. op[0] 은 덧셈의 개수 / op[1] 은 뺄셈의 개수 / op[2] 는 곱셈의 개수 / op[3] 은 나눗셈의 개수를 뜻합니다.

2. 그리고 나서 주어진 연산자들의 순열을 출력하기 위해서 operator라는 op[0]부터 차례대로 가지고 있는 번호를 넣었습니다. 3번째 예제를 예로 들면 op[] = { 2, 1, 1, 1 } 인데 이것을 operator에 차례대로 00123 을 넣습니다. 그러면 0이 2개이므로 덧셈이 2개, 나머지가 1개이므로 나머지 연산자들은 1개를 가지고 있는 것을 알 수 있습니다.

3. 그리고 operator 의 모든 순열을 구하는 perm() 을 시행하면 문제에서 연산자의 총 개수는 N-1개라고 했으므로 depth 가 N-1 일 때, 나올 수 있는 모든 순열의 경우의수가 출력됩니다.

4. 각 경우의수가 operator[] 에 저장 되면, 주어진 순열 A[]와 함께 계산하기 위해서 ArrayList 인 temp에 넣습니다. 여기에서 temp에 예를들어 1 0 2 0 3 1 4 2 5 3 6 이 들어가 있으면 짝수에 있는 숫자가 연산자를 뜻하기 때문에 이것이 뜻하는 것은 1 + 2 + 3 - 4 x 5 / 6 이 됩니다.

5. temp에 순열과 연산자가 들어가면 계산을 하기 위해서 calc() 함수를 시행하여 계산값을 리턴합니다.

6. 그래서 나온 계산 값을 차례대로 ans 라는 ArrayList에 넣어서 최댓값과 최솟값을 구하여 출력했습니다. 근데 여기에서 ArrayList에 안넣고 바로 나온 값을 Math.max() 와 Math.min() 을 해서 저장하여 출력하고 싶었는데 왜ArithmeticException이 나오는지 모르겠습니다......... 0으로 나누었을 때 나오는 예외라고 하는데 어디에서 0으로 나누었는지 잘 모르겠습니다. 이유를 아시는 분은 댓글로 알려주시면 감사하겠습니다 ! 어쨋든 그래서 결국 최댓값과 최솟값을 구해서 정답이 나왔습니다.

---

import java.util.Scanner;
import java.util.ArrayList;

// 14888 연산자 끼워넣기
public class Main {
	static int N, MAX = -987987987, MIN = 987987987;
	static int [] A, op, operator;
	static ArrayList<Integer> temp;
	static ArrayList<Integer> ans  = new ArrayList<Integer>();
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		A = new int[N];
		
		op = new int[4];
		operator = new int[N-1];
		for(int i=0; i<N;i++) {
			A[i]=sc.nextInt();
		}
		for(int i=0; i<4; i++) {
			op[i] = sc.nextInt();
		}
		int idx = 0;
		for(int i=0; i<4; i++) {
			if(op[i] != 0) {
				for(int j=0; j<op[i]; j++) {
					operator[idx++] = i;
				}
			}
		}
		
		perm(operator, 0);
		
		for(int i=0; i<ans.size(); i++) {
			if(MAX < ans.get(i)) MAX = ans.get(i);
			if(MIN > ans.get(i)) MIN = ans.get(i);
		}
		System.out.println(MAX);
		System.out.println(MIN);
	}
	
	public static void perm(int[] oper, int depth) {
		if(depth == N-1) {
			temp = new ArrayList<Integer>();
			for(int i=0; i<N; i++) {
				temp.add(A[i]);
				if(i==N-1) break;
				temp.add(operator[i]);
			}
			ans.add(calc(temp));
			
//			for(int i=0; i<temp.size(); i++) {
//				System.out.print(temp.get(i));
//			}
//			System.out.println();
			
//			MIN = Math.min(calc(temp), MIN);
//			MAX = Math.max(calc(temp), MAX);
			return;
		}
		
		for(int i=depth; i<N-1; i++) {
			swap(oper, i, depth);
			perm(oper, depth+1);
			swap(oper, i, depth);
		}
		
	}
	public static void swap(int [] arr, int s, int e) {
		int temp = arr[s];
		arr[s] = arr[e];
		arr[e] = temp;
	}
	
	public static int calc(ArrayList<Integer> list) {
		for(int i=1; i<list.size()-1; i+=2) {
			if(list.get(i) == 0) {
				// + 일때
				int result = list.get(i-1) + list.get(i+1);
				list.set(i+1, result);
			} else if(list.get(i)==1) {
				// - 일때
				int result = list.get(i-1) - list.get(i+1);
				list.set(i+1, result);
			} else if(list.get(i)==2) {
				// x 일때
				int result = list.get(i-1) * list.get(i+1);
				list.set(i+1,  result);
			} else {
				// 나누기 일때
				int result = list.get(i-1) / list.get(i+1);
				list.set(i+1, result);
			}
		}
		return list.get(list.size()-1);
	}
}