DFS [BOJ14888] 연산자 끼워넣기

https://www.acmicpc.net/problem/14888

연산자 목록이 주어지면 무작위의 순서로 숫자들 사이에 끼워넣었을 때 어떤 값이 가장 크고 작은지를 반환한다.

문제를 보자마자 일단 완전탐색으로 경우의 수를 모두 받아야 겠다고 생각했다.
그러므로 연산자들의 순열이 필요했다.

	public static void dfs(int L) {

		if (L == (n - 1)) {
			int ans = calculate(nums, res);
			max = ans>max ? ans : max; 
			min = ans<min ? ans : min; 
		}

		else {
			for (int j = 0; j < 4; j++) {
				if (cals[j] != 0) {
					res[L] = j;
					cals[j] -= 1;
					dfs(L + 1);
					cals[j] += 1;
				}

			}
		}
	}

구현해본 DFS 함수부이다. _+,-,*,/ 를 가지는 크기 4의 cals 배열에 들어있는 연산자들을 모두 순열로 뽑아내었다.
겹치는 연산자가 있다고 하더라도 어차피 연산자 배열에서 뽑아가는 것이기 때문에 중복이 되지 않는다. (솔직히 정확히 왜 중복이 안되고 잘 실행되는지 내가 짰는데도 햇갈린다...)

어쨌든 연산자의 수가 각각 들어있는 배열을 순회하면서 빼낼 수 있는 연산자가 있다면 빼내고 연산자 값을 res배열에 집어넣는다.
그리고 연산자가 빠져있는 배열이 적용되어있고, 탐색된 가짓수(Level)이 1이 증가된 DFS를 재귀적으로 호출한다.

이렇게 모든 경우의 수를 다 돌 수 있다.
참고로 조합이 아니라 순열인 경우에서는 빼주었던 연산자를 같은 레벨에서는 아직 사용 안한 것으로 판단되고 있기 때문에 반환해주어야 한다.

package week4;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class BruteForce_P14888 {

	static int n;
	static int nums[];
	static int cals[];
	static int res[];
	static int max = Integer.MIN_VALUE;
	static int min = Integer.MAX_VALUE;
	static int test = 0;
	

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		n = Integer.parseInt(br.readLine());
		nums = new int[n];
		cals = new int[4];
		res = new int[n - 1];

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

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

		dfs(0);
		System.out.println(max);
		System.out.println(min);
		System.out.println(test);
	}

	public static void dfs(int L) {

		if (L == (n - 1)) {
			int ans = calculate(nums, res);
			test++;
			max = ans>max ? ans : max; 
			min = ans<min ? ans : min; 
		}

		else {
			for (int j = 0; j < 4; j++) {
				if (cals[j] != 0) {
					res[L] = j;
					cals[j] -= 1;
					dfs(L + 1);
					cals[j] += 1;
				}

			}
		}
	}

	public static int calculate(int[] nums, int[] res) {
		int ans = nums[0];
		for (int i = 0; i < res.length; i++) {
			int ops = res[i];
			if (ops == 0)
				ans += nums[i + 1];
			else if (ops == 1)
				ans -= nums[i + 1];
			else if (ops == 2)
				ans *= nums[i + 1];
			else if (ops == 3) {
				if (ans < 0) {
					ans = -ans;
					ans /= nums[i + 1];
					ans = -ans;
				} else
					ans /= nums[i + 1];
			}
		}
		return ans;
	}

}