문제

백준 14888 연산자 끼워넣기 문제 보러가기



문제점 해결

해당 문제는 연산자의 순열로 해결할 수 있으며 주의해야 할 부분은 결과값의 범위이다. 처음엔 최솟값을 Integer.MAX_VALUE로 최댓값은 0으로 초기화 하였으나 피연산자가 ‘1’과 ‘2’이고 연산자가 ‘-‘인 경우 최댓값은 -1인데(주어진 수의 순서를 바꿀 수 없음!) 0으로 초기화된 최댓값으로 인해 틀린 결과가 나온다. 제대로된 결과를 얻기 위해선 최솟값(min)은 1000000000, 최댓값(max)은 -1000000000으로 초기화 해줘야 한다.



풀이

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

public class Main {
	static int N;
	static int[] nums, opers;
	static int[] res;
	static int max, min;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

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

		int index = 0;
		opers = new int[N - 1];
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < 4; i++) {
			int end = Integer.parseInt(st.nextToken());
			if (end == 0)
				continue;

			for (int j = 0; j < end; j++) {
				opers[index++] = i;
			}
		}

		res = new int[N - 1];
		max = -1000000000;
		min = 1000000000;

		permutation(new boolean[N - 1], 0);

		System.out.println(max);
		System.out.println(min);
	}

	public static void permutation(boolean[] used, int index) {
		if (index == used.length) {
			int sum = nums[0];
			for (int i = 0; i < N - 1; i++) {
				sum = cal(sum, nums[i + 1], res[i]);
			}

			max = Math.max(max, sum);
			min = Math.min(min, sum);
			return;
		}

		for (int i = 0; i < used.length; i++) {
			if (!used[i]) {
				used[i] = true;
				res[index] = opers[i];
				permutation(used, index + 1);
				res[index] = -1;
				used[i] = false;
			}
		}
	}

	public static int cal(int a, int b, int oper) {
		switch (oper) {
		case 0:
			return a + b;
		case 1:
			return a - b;
		case 2:
			return a * b;
		default:
			if (a < 0) {
				a *= -1;
				return (a / b) * -1;
			}
			return a / b;
		}
	}
}