[Silver1-JAVA] 백준 14888 - 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

 

🤔 문제 풀이

제법 쉬웠던 완전 탐색 문제였다.

전체 숫자에 대해 수행할 수 있는 모든 연산자를 도입하여 최대와 최소값을 구하면 된다.

아마 별다른 최대, 최소를 구할 수 있는 방법이 없을 것이라 생각하고 고민없이

깊이우선 탐색 알고리즘인 DFS 알고리즘을 사용해 풀었다.

음수와 양수의 나눗셈 같은 경우 문제에서 양수 끼리 몫을 취하고 음수로 바꾸어주라고 해서

나누어지는 수를 절댓값으로 치환하고 나누어준뒤 음수로 바꾸었다.

🚨CODE

import java.util.*;
import java.io.*;
import java.math.BigInteger;

public class Main {
	static int[] num;
	static int n;
	static int min = Integer.MAX_VALUE;
	static int max = Integer.MIN_VALUE;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		num = new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i = 0; i<n; i++) {
			num[i] = Integer.parseInt(st.nextToken());
		}
		
		int[] op = new int[4];
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i<4; i++) {
			op[i] = Integer.parseInt(st.nextToken());
		}
		
		dfs(op, num[0], 1);
		System.out.println(max);
		System.out.println(min);
	}
	public static void dfs(int[] op, int sum, int depth) {
		if(depth == n) {
			max = Math.max(sum, max);
			min = Math.min(sum, min);
			return;
		}
		
		for(int i = 0; i<4; i++) {
			if(op[i] == 0)
				continue;
			
			op[i]--;
			// 덧셈이라면
			if(i == 0)
				dfs(op, sum + num[depth], depth+1);
			// 뺄셈이라면
			else if(i == 1)
				dfs(op, sum - num[depth], depth+1);
			// 곱셈이라면
			else if(i == 2)
				dfs(op, sum * num[depth], depth+1);
			// 나눗셈이라면
			else {
				// 음수의 나눗셈이라면
				if(sum < 0) {
					dfs(op, -(Math.abs(sum) / num[depth]), depth+1);
				}else {
					dfs(op, sum / num[depth], depth+1);
				}
			}
			op[i]++;
		}
	}
}