[BOJ] 14888 연산자 끼워넣기 - Java

문제

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

14888번: 연산자 끼워넣기

 

---

풀이

• N개의 수와 N-1개의 연산자가 주어졌을 때 만들 수 있는 계산식의 결과 중 최소값 구하기
• 수와 수 사이에 연산자를 넣어서 결과를 계산한다
• 연산자 순서가 유의미하고 중복은 허용되지 않으므로 순열을 사용해서 연산자 순서 정하기

---

코드

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	static int[] mix, num;
	static boolean[] used;
	static ArrayList<Integer> list;
	static int min, max;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		num = new int[n];
		mix = new int[n-1];
		list = new ArrayList<>();
		
		min = Integer.MAX_VALUE;
		max = Integer.MIN_VALUE;
		
		for(int i=0; i<n; i++) {
			num[i] = sc.nextInt();
		}
		
		for(int i=0; i<4; i++) {
			int o = sc.nextInt();
			if(o != 0) {
				for(int j=0; j<o; j++) {
					list.add(i);
				}
			}
		}

		used = new boolean[list.size()];
		
		perm(0);
		
		System.out.println(max);
		System.out.println(min);
		
	}

	private static void perm(int cnt) {
		if(cnt == mix.length) {
			cal(mix);
			return;
		}
		
		for(int i=0; i<list.size(); i++) {
			if(used[i]) continue;
			mix[cnt] = list.get(i);
			used[i] = true;
			perm(cnt+1);
			used[i] = false;
		}
	}

	private static void cal(int[] mix) {
		int result = num[0];
		
		for(int i=0; i<mix.length; i++) {
			switch(mix[i]){
				case 0:
					result += num[i+1];
					break;
				case 1:
					result -= num[i+1];
					break;
				case 2:
					result *= num[i+1];
					break;
				case 3:
					if(result > 0) {
						result /= num[i+1];
						break;
					}
					else if(result < 0){
						result *= (-1);
						result /= num[i+1];
						result *= (-1);
						break;
					}
			}	
		}
		
		if(result <= min) {
			min = result;
		}
		if(result >= max) {
			max = result;
		}
	}
}

• 각각의 연산자가 몇 개가 입력으로 들어올지 모르기 때문에 list 사용
• + : 0, - : 1 , * : 2, / : 3으로 케이스를 나눠서 계산 수행
• 최소 값 갱신하며 가장 작은 결과 값 구하기