문제

BOJ 14888: 연산자 끼워넣기 https://www.acmicpc.net/problem/14888

풀이

• 연산자 입력이 2 1 1 1 이런 식으로 들어오기 때문에 ArrayList를 만들어 덧셈: 0, 뺄셈: 1, 곱셈: 2, 나눗셈: 3 이런 식으로 0 0 1 2 3 순으로 넣어준다.
• 백트래킹 메소드로 들어가 nOper 배열에 1 0 2 0 3 이런 식으로 새로운 조합을 만들어준다.
• 숫자로 구분 되어진 연산자를 계산할 수 있도록 operation 메소드를 만들어 처리한다.

코드

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

public class Main {
	
	static int[] nOper;
	static ArrayList<Integer> list = new ArrayList<>();
	static boolean[] isChecked;
	static int max, min;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine()); // 수의 개수
		int[] arr = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for(int i=0; i<arr.length; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int[] oper = new int[4]; // 덧셈: 0, 뺄셈: 1, 곱셈: 2, 나눗셈: 3
		st = new StringTokenizer(br.readLine(), " ");
		for(int i=0; i<oper.length; i++) {
			oper[i] = Integer.parseInt(st.nextToken());
		}
		// 연산자를 차례로 리스트에 넣는다.
		for(int i=0; i<oper.length; i++) {
			for(int j=0; j<oper[i]; j++) {
				list.add(i);
			}
		}
		
		nOper = new int[N-1]; // 새로운 조합을 만들어 낼 배열 
		isChecked = new boolean[N-1]; // 방문처리 해 줄 배열
		max = Integer.MIN_VALUE;
		min = Integer.MAX_VALUE;
		
		bt(arr, list, 0);
		
		System.out.println(max);
		System.out.println(min);
	}
	
	static void bt(int[] arr, ArrayList<Integer> list, int depth) {
		int sum = 0;
		if(depth == list.size()) {
			int beforeNum = arr[0];
			for(int i=0; i<list.size(); i++) {
				int afterNum = arr[i+1];
				beforeNum = operation(beforeNum, nOper[i], afterNum);
			}
			sum = beforeNum;
			max = Math.max(sum, max);
			min = Math.min(sum, min);
		}
		
		for(int i=0; i<list.size(); i++) {
			if(!isChecked[i]) {
				isChecked[i] = true;
				nOper[depth] = list.get(i);
				bt(arr, list, depth + 1);
				isChecked[i] = false;
			}
		}
		
	}
	
	static int operation(int beforeNum, int oper, int afterNum) {
		switch(oper) {
			case 0: return beforeNum + afterNum;
			case 1: return beforeNum - afterNum;
			case 2: return beforeNum * afterNum;
			case 3: return beforeNum / afterNum;
		}
		
		return 0;
	}
	
}

정리

• 백트래킹을 구현하는데 어렵지 않았다.