[BOJ 14888] 연산자 끼워넣기

문제

• BOJ 14888
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

1.+,-,,/에 대한 경우의 수를 순열로 구한다. ⇒ permutation()
- +,-,,/가 순서대로 들어오므로 각각 0,1,2,3으로 생각해서 operList에 담는다.
- operList에 대하여 N-1개의 순열을 구해서 selected에 저장한다.
2.구한 연산자에 대하여 계산을 진행한다. ⇒ calculate()
- 입력받은 숫자를 돌면서 selected에서 연산자를 하나씩 꺼내서 차례대로 계산을 진행해준다.
- 계산 끝난 후 최대값과 최소값을 저장한다. ddsd

import java.io.*;
import java.util.*;

class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int maxAns = Integer.MIN_VALUE;
	static int minAns = Integer.MAX_VALUE;
  static int N;
  static int[] numbers;
	static List<Integer> operList;
    
	public static void main(String[] args) throws IOException {
		N = Integer.parseInt(br.readLine());
		numbers = new int[N];
		operList = new ArrayList<>();
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) numbers[i] = Integer.parseInt(st.nextToken());G

		st = new StringTokenizer(br.readLine());
		for(int i=0; i<4; i++) {
			int cnt = Integer.parseInt(st.nextToken());
			for(int j=0; j<cnt; j++) {
				operList.add(i); //0:+, 1:-, 2:x, 3:/
			}
		}//End input
		
		visited = new boolean[operList.size()];
		selected = new int[operList.size()];
		
		//1. 연산자 순열 구하기 n-1Pn-1
		permutation(0);
		System.out.println(maxAns);
		System.out.println(minAns);
	}
	
	static boolean[] visited;
	static int[] selected;
	
	private static void permutation(int idx) {
		if(idx == N-1) {
			//2. 연산 하기
			int result = numbers[0];
			for(int i=0; i<N-1; i++) {
				result = calculate(selected[i], result, numbers[i+1]);
			}
			maxAns = Math.max(result, maxAns);
			minAns = Math.min(result, minAns);
			return;
		}
		
		for(int i=0; i<operList.size(); i++) {
			if(!visited[i]) {
				selected[idx] = operList.get(i);
				visited[i] = true;
				permutation(idx+1);
				visited[i] = false;
			}
		}
	}

	private static int calculate(int oper, int a, int b) {
		int result = 0;
		
		switch(oper) {
		case 0: result = a + b; break;
			
		case 1: result = a - b; break;
			
		case 2: result = a * b; break;
			
		case 3: result = a / b; break;
		}
		return result;
	}
}