백준 14888 : 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

[ 문제풀이 ]

간단한 문제이다. 주어진 연산자로 만들 수 있는 모든 경우의 수를 다 탐색하여 최댓값과 최솟값을 구해주면 된다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;

	static int N, min, max;
	static int[] num;
	static boolean[] check;
	static List<Integer> operators;

	public static void main(String[] args) throws IOException {
		N = Integer.parseInt(br.readLine());
		check = new boolean[N];
		max = -(int)1e9;
		min = (int)1e9;

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

		operators = new ArrayList<>();
		st = new StringTokenizer(br.readLine());
		//연산자를 리스트에 담아줌
		// '+' : 0 / '-' : 1 / '*' : 2 / '/' : 3
		for (int i = 0; i < 4; ++i) {
			int count = Integer.parseInt(st.nextToken());
			for (int j = 0; j < count; ++j) {
				operators.add(i);
			}
		}

		solve(num[0], 1, N - 1);
		bw.write(max + "\n" + min + "\n");
		bw.flush();bw.close();br.close();
	}

	//주어진 연산자로 만들 수 있는 모든 경우의 수
	public static void solve(int value, int idx, int cnt) {
		if (cnt == 0) {
			max = Math.max(max, value);
			min = Math.min(min, value);
			return;
		}

		for (int i = 0; i < N - 1; ++i) {
			if (check[i]) continue;
			
			check[i] = true;
			int operator = operators.get(i);

			if (operator == 0) {
				solve(value + num[idx], idx + 1, cnt - 1);
			} else if (operator == 1) {
				solve(value - num[idx], idx + 1, cnt - 1);
			} else if (operator == 2) {
				solve(value * num[idx], idx + 1, cnt - 1); 
			} else {
				solve(value / num[idx], idx + 1, cnt - 1);
			}

			check[i] = false;
		}
	}
}