[JAVA] 백준 14888번 : 연산자 끼워넣기 (삼성 SW 역량 테스트 기출 문제)

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

14888번: 연산자 끼워넣기

문제

브루트포스 문제 인데 DFS 탐색을 이용하여 문제를 해결하였다.

 

해결 방안

숫자의 위치는 고정이고 연산자 우선순위도 무시하므로 숫자간 모든 경우의 연산자를 넣어 각각의 sum값들을 비교하여 최대 최소값을 구하는 문제이다.

덧셈, 뺄셈, 곱셈, 나눗셈의 갯수의 합이 N-1 개이므로 각각의 갯수들을 고려하여 DFS 탐색을 해주면된다.
그리고 기저사례를 depth가 N-1인 경우로 하며 계산된 sum값의 max, min 값을 구해준다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

// 연산자 끼워넣기
// 연산자 우선 순위 무시하고 앞에서부터 진행
// 나눗셈은 몫만 취함(음수 이면 양수로 바꾼뒤 몫을 취하고 그 몫을 음수로 바꿈)
// 식의 결과가 최대인 값과 최소인 값을 구함
public class Main {

	static int N; // 수의 갯수(2~11)
	static int[] a; // a1~an
	
	static int[] operatorCnts; // 덧셈, 뺄셈, 곱셈, 나눗셈
	
	// (-10억~10억)
	static int max = Integer.MIN_VALUE;
	static int min = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		a = new int[N+1];
		
		String str;
		str = br.readLine();
		StringTokenizer st = new StringTokenizer(str, " ");
		for(int i=1; i<N+1; i++) {
			a[i] = Integer.parseInt(st.nextToken());
		}
		
		str = br.readLine();
		operatorCnts = new int[4];
		for(int i=0; i<4; i++) {
			operatorCnts[i] = Integer.parseInt(str.split(" ")[i]);
		}
		
		// =========== 입력 끝 ============
		dfs(0, a[1]);
		
		System.out.println(max);
		System.out.println(min);
	}
	
	static void dfs(int depth, int sum) {

		if(depth >= N-1) {
			max = Math.max(max, sum);
			min = Math.min(min, sum);
			return;
		}
		else {
			// 덧셈
			if(operatorCnts[0] > 0) {
				operatorCnts[0]--;
				dfs(depth+1, sum+a[depth+2]);
				operatorCnts[0]++;
			}
			// 뺄셈
			if(operatorCnts[1] > 0) {
				operatorCnts[1]--;
				dfs(depth+1, sum-a[depth+2]);
				operatorCnts[1]++;
			}
			// 곱셈
			if(operatorCnts[2] > 0) {
				operatorCnts[2]--;
				dfs(depth+1, sum*a[depth+2]);
				operatorCnts[2]++;
			}
			// 나눗셈
			if(operatorCnts[3] > 0) {
				operatorCnts[3]--;
				if(sum < 0) {
					sum *= -1;
					dfs(depth+1, (sum/a[depth+2]) * -1);
					sum *= -1;
				}
				else {
					dfs(depth+1, sum/a[depth+2]);
				}
				operatorCnts[3]++;
			}
		}
	}
}