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

문제 (브루트포스 알고리즘)

 

14888번: 연산자 끼워넣기

 

 

문제 풀이

 

사용되는 연산자를 해당 연산자의 인덱스번호를 perm_data에 담는다.

예를 들어 '+'가 1개, 'x'가 2개 이면 perm_data = {0, 2, 2} 이런 식으로 담기게 된다.

이 배열을 조합하여 모든 경우에 해당 되는 연산자 순서를 구하고, 구하는 경우마다 계산결과를 구해 답을 갱신한다.

 

 

소스 코드

 

import java.util.Scanner;

public class b_14888 {
	
	static int min = Integer.MAX_VALUE;
	static int max = Integer.MIN_VALUE;
	static int N;
	static int[] An;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int idx = 0;
		N = sc.nextInt();
		An = new int[N];
		int[] perm_data = new int[N-1];
		int[] result = new int[N];
		boolean[] visited = new boolean[N];
		
		for(int i = 0; i < N; i++)
			An[i] = sc.nextInt();
		
		for(int i = 0; i < 4; i++) {
			int operNum = sc.nextInt();
			if(operNum > 0) {
				for(int j = 0; j < operNum; j++)
					perm_data[idx++] = i;
			}
		}
		
		permutation(N-1, 0, perm_data, result, visited);
		System.out.println(max);
		System.out.println(min);
		sc.close();
	}
	
	public static void permutation(int n, int depth, int[] data, int[] result, boolean[] visited) {
		if(depth == n) {
			confirm(result);
			return;
		}
		
		for(int i = 0; i < n; i++) {
			if(visited[i] == false) {
				result[depth] = data[i];
				visited[i] = true;
				permutation(n, depth+1, data, result, visited);
				visited[i] = false;
			}
		}
	}
	
	public static void confirm(int[] result) {		
		int idx = 0;
		int ans = An[idx++];
		
		for(int i = 0; i < N-1; i++) {
			if(result[i] == 0) 
				ans += An[idx];
			else if(result[i] == 1)
				ans -= An[idx];
			else if(result[i] == 2)
				ans *= An[idx];
			else
				ans /= An[idx];
			idx++;
		}
		
		if(ans < min)
			min = ans;
		if(ans > max)
			max = ans;
	}
}