[Java] BOJ14888_연산자 끼워넣기

www.acmicpc.net/problem/14888

14888번: 연산자 끼워넣기

---

연산자를 순서에 상관있게 숫자 사이에 끼워 넣고 식을 계산하여 최댓값과 최솟값을 구하는 문제이다. '-', '/' 연산 등이 존재하여 가지치기를 할 수 없는 문제이다.

 

연산자를 순서에 맞도록 쉽게 사용하기 위해 oper배열을 만들어주고 연산자 수만큼 순서대로 담아주었다.

+는 0, -는 1, *는 2, /는 3이라 할 때 예제 3같은 경우 oper배열에 [0, 0, 1, 2, 3]이 담기게 된다.

 

순열을 구해주고 연산자를 넣어 계산해주면 된다. 이 때 나눗셈을 문제에 주어진 조건에 맞추어하도록 주의한다.

"양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다." 

 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	static int N;
	static int oper[];
	static int[] arr;
	static int max = Integer.MIN_VALUE;
	static int min = Integer.MAX_VALUE;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr = new int[N];
		oper = new int[N-1];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine());
		int idx = 0;
		for (int i = 0; i < 4; i++) {
			int num = Integer.parseInt(st.nextToken());
			for (int j = 0; j < num; j++) {
				oper[idx++] = i;
			}
		}
		permutation(0, new int[N-1], new boolean[N-1]);
		System.out.println(max);
		System.out.println(min);
	}

	public static void permutation(int cnt, int[] result, boolean[] visit) {
		if(cnt == N-1) {
			int res = arr[0];
			int idx = 1;
			for (int i = 0; i < N-1; i++) {
				switch(oper[result[i]]) {
				case 0: // +
					res += arr[idx++];
					break;
				case 1: // -
					res -= arr[idx++];
					break;
				case 2: // *
					res *= arr[idx++];
					break;
				case 3: // /
					if(res < 0) res = (Math.abs(res) / arr[idx++]) * -1;
					else res /= arr[idx++];
					break;
				}
			}
			max = Math.max(res, max);
			min = Math.min(res, min);
			return;
		}
		for (int i = 0; i < N-1; i++) {
			if(!visit[i]) {
				visit[i] = true;
				result[cnt] = i;
				permutation(cnt+1, result, visit);
				visit[i] = false;
			}
		}
	}
}