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

[문제]

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

 

 

[소스 코드]

import java.io.*;
import java.util.*;
public class Main {
	static int n;
	static int[] nums;
	static int min = Integer.MAX_VALUE;
	static int max = Integer.MIN_VALUE;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		nums = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine());
		int plus = Integer.parseInt(st.nextToken());
		int minus = Integer.parseInt(st.nextToken());
		int multi = Integer.parseInt(st.nextToken());
		int divide = Integer.parseInt(st.nextToken());
		cal(plus,minus,multi,divide,0,0);
		System.out.println(max);
		System.out.println(min);
	}
	private static void cal(int plus,int minus,int multi,int divide,int cnt,int sum) {
		if(cnt==n) {
			max = Math.max(max, sum);
			min = Math.min(min, sum);
			return;
		}
		if(cnt==0) {
			if(plus!=0) cal(plus-1,minus,multi,divide,2,nums[0]+nums[1]);
			if(minus!=0) cal(plus,minus-1,multi,divide,2,nums[0]-nums[1]);
			if(multi!=0) cal(plus,minus,multi-1,divide,2,nums[0]*nums[1]);
			if(divide!=0) cal(plus,minus,multi,divide-1,2,nums[0]/nums[1]);
			return;
		}
		if(plus!=0) cal(plus-1,minus,multi,divide,cnt+1,sum+nums[cnt]);
		if(minus!=0) cal(plus,minus-1,multi,divide,cnt+1,sum-nums[cnt]);
		if(multi!=0) cal(plus,minus,multi-1,divide,cnt+1,sum*nums[cnt]);
		if(divide!=0) cal(plus,minus,multi,divide-1,cnt+1,sum/nums[cnt]);
	}
}