[JAVA]백준 14888번: 연산자 끼워넣기

www.acmicpc.net/problem/14888

 

1. 문제 설명

 

숫자와 그 사이에 들어갈 연산자의 개수가 주어질 때 만들 수 있는 식의 최댓값과 최솟값을 구하는 문제이다.

 

간단하게 재귀함수로 풀 수 있다.

 

연산자의 개수가 1보다 크고 10보다 작은 입력이 들어오므로 최악의 경우 4^10번의 계산이 필요하나 최악의 경우에도 시간을 통과할 수 있기 때문에 재귀 함수 알고리즘을 사용했다.

 

(같은 연산자라 하더라도 순서에 따라 결과가 다르다고 생각했을 경우가 4^10이므로 실제로는 이보다 더 작을 것이다.)

 

코드에서는 함수 인자에 ArrayList를 넣어 사용했지만 static 변수로 사용하는 편이 더 좋을 것 같다.

 

2. 코드

 

 

	import java.lang.reflect.Array;
	import java.util.ArrayList;
	import java.util.Scanner;
	public class Main {
	public static int [] temp_answer={1000000000,-1000000000};
	public static void main(String[] args) {
	Scanner scan=new Scanner(System.in);
	int num;
	num=scan.nextInt();
	ArrayList<Integer> num_list=new ArrayList<Integer>();
	int [] operator=new int[4];
	for(int i=0;i<num;i++)
	num_list.add(scan.nextInt());
	for(int i=0;i<4;i++)
	operator[i]=scan.nextInt();
	int sum=num_list.get(0);
	num_list.remove(0);
	sum_calculator(num_list,operator,sum);
	System.out.println(temp_answer[1]+"\n"+temp_answer[0]);
	scan.close();
	}
	public static void sum_calculator(ArrayList<Integer> num_list, int[] operator,int sum){
	if(num_list.size()==0){
	temp_answer[0]=Math.min(sum,temp_answer[0]);
	temp_answer[1]=Math.max(sum,temp_answer[1]);
	return;
	}
	int value=num_list.get(0);
	num_list.remove(0);
	for(int i=0;i<4;i++)
	{
	if(operator[i]!=0)
	{
	int temp_sum=sum;
	operator[i]--;
	if(i==0)
	temp_sum+=value;
	else if(i==1)
	temp_sum-=value;
	else if(i==2)
	temp_sum*=value;
	else temp_sum/=value;
	sum_calculator(num_list,operator,temp_sum);
	operator[i]++;
	}
	}
	num_list.add(0,value);
	return;
	}
	}

view raw 14888.java hosted with ❤ by GitHub