[BaekJoon] 14888 백준 연산자 끼워넣기

 

 

모든 경우의수를 알아야 하기 때문에 dfs로 풀었다. 

 

import java.util.Scanner;

public class Main {
	static int min = Integer.MAX_VALUE;
	static int max = Integer.MIN_VALUE;
	static int n;
	static int[] op;
	static int[] arr;
	
	public static void main(String args[]) {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		
		arr = new int[n];
		op = new int[4];
		//+ - * /
		
		for(int i = 0; i<n ;i++) {
			arr[i] = scan.nextInt();
		}
		
		for(int i = 0; i<4; i++) {
			op[i] = scan.nextInt();
		}
		
		dfs(1, 0, 0, 0, 0, arr[0]);
		
		System.out.println(max);
		System.out.println(min);
	}
	
	public static void dfs(int index, int p, int m, int mul, int div, int value) {
		if(index > n-1) {
			if(value > max)
				max = value;
			
			if(value <  min)
				min = value;
			
			
			return;
		}
		
		if(p < op[0]) {
			dfs(index+1, p+1, m, mul, div, value+arr[index]);
		}
		
		if(m < op[1]) {
			dfs(index+1, p, m+1, mul, div, value-arr[index]);
		}
		
		if(mul < op[2]) {
			dfs(index+1, p, m, mul+1, div, value*arr[index]);
		}
		
		if(div < op[3]) {
			dfs(index+1, p, m, mul, div+1, value/arr[index]);
		}
	}

}