14888_연산자 끼워넣기 (JAVA)

14888번: 연산자 끼워넣기

 

① 순열 이용

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static List<Integer> calList = new ArrayList<>();
	static int[] num;
	static int ans_min = Integer.MAX_VALUE;
	static int ans_max = Integer.MIN_VALUE;

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(br.readLine());
		num = new int[n];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++){
			num[i] = Integer.parseInt(st.nextToken());
		}

		st = new StringTokenizer(br.readLine());
		for(int i=0; i<4; i++){
			int temp = Integer.parseInt(st.nextToken());
			while(temp-- > 0){
				calList.add(i);
			}
		}

		List<Integer> perm = new ArrayList<>();
		boolean[] visited = new boolean[n-1];
		permutation(perm, visited);

		System.out.println(ans_max);
		System.out.println(ans_min);
		br.close();
	}

	private static void permutation(List<Integer> perm, boolean[] visited){
		if(perm.size()==num.length-1){
			int x = num[0];
			for(int i=0; i<perm.size(); i++){
				if(perm.get(i)==0) x += num[i+1];
				if(perm.get(i)==1) x -= num[i+1];
				if(perm.get(i)==2) x *= num[i+1];
				if(perm.get(i)==3) x /= num[i+1];
			}
			ans_max = Math.max(ans_max, x);
			ans_min = Math.min(ans_min, x);
			return;
		}

		for(int i=0; i<calList.size(); i++){
			if(!visited[i]){
				visited[i] = true;
				perm.add(calList.get(i));
				permutation(perm, visited);

				visited[i] = false;
				perm.remove(perm.size()-1);
			}
		}
	}
}

1. 입력받은 연산자 개수를 덧셈=0, 뺄셈=1, 곱셈=2, 나눗셈=3 으로 표현하여, 해당 연산자 개수만큼 calList에 add한다.

2. 연산자가 들어있는 리스트를 자기자신을 제외하고, 순서있게 순열로 정렬한다.

3. 연산자가 정렬이 될 때마다 계산하여 최대값과 최소값을 계산한다.

 

 

 

② DFS 이용

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int[] num;
	static int[] cal;
	static int ans_min = Integer.MAX_VALUE;
	static int ans_max = Integer.MIN_VALUE;

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(br.readLine());
		num = new int[n];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++){
			num[i] = Integer.parseInt(st.nextToken());
		}

		cal = new int[4];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<4; i++){
			cal[i] = Integer.parseInt(st.nextToken());
		}

		dfs(0, num[0]);

		System.out.println(ans_max);
		System.out.println(ans_min);
		br.close();
	}

	private static void dfs(int idx, int temp){
		if(idx == num.length-1){
			ans_max = Math.max(ans_max, temp);
			ans_min = Math.min(ans_min, temp);
			return;
		}

		for(int i=0; i<4; i++){
			if(cal[i] > 0){
				cal[i]--;

				if(i==0) dfs(idx+1, temp+num[idx+1]);
				if(i==1) dfs(idx+1, temp-num[idx+1]);
				if(i==2) dfs(idx+1, temp*num[idx+1]);
				if(i==3) dfs(idx+1, temp/num[idx+1]);

				cal[i]++;
			}
		}
	}
}

1. 입력받은 숫자배열 num의 인덱스와 계산결과 를 인자로 하는 dfs() 함수를 구현한다.

2. 연산자 개수가 0보다 큰 경우,

   해당 연산자 개수를 -1 해준 상태로 dfs를 돌리고, 다시 +1 해주어 계산의 모든 경우를 탐색한다.