[백준/Java] 14888 연산자 끼워넣기

조건

1. N개로 이루어진 자연수의 수열을 받는다

2. N-1개 만큼의 연산자의 수를 준다

3. 연산자의 수는 +, -, *, / 순으로 입력해준다.

4. 만들 수 있는 수의 최대, 최소를 구하여라

입력 예제

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {
 
	public static int MAX = Integer.MIN_VALUE;	// 최댓값 
	public static int MIN = Integer.MAX_VALUE;	// 최솟값 
	public static int[] operator = new int[4];	// 연산자 개수를 받기 위한 배열
	public static int[] arr;					// 숫자 
	public static int N;						// 숫자 개수 
 
	public static void main(String[] args) throws IOException {
 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		N = Integer.parseInt(br.readLine());
		number = new int[N];
 
		// 숫자 입력 
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			number[i] = Integer.parseInt(st.nextToken());
		}
 
		// 연산자 입력 
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < 4; i++) {
			operator[i] = Integer.parseInt(st.nextToken());
		}
 
		dfs(number[0], 1);
 
		System.out.println(MAX);
		System.out.println(MIN);
 
	}
 
	public static void dfs(int num, int idx) {
		if (idx == N) {
			MAX = Math.max(MAX, num);
			MIN = Math.min(MIN, num);
			return;
		}
 
		for (int i = 0; i < 4; i++) {
			// 연산자 개수가 1개 이상인 경우
			if (operator[i] > 0) {
 
				// 해당 연산자를 1 감소시킨다.
				operator[i]--;
 
				switch (i) { //switch문을 활용해 연산자 배열의 값을 확인하고 
               			//해당 연산자에 따라 계산을 해주고 다시 재귀함수를 호출한다.
				case 0:	dfs(num + arr[idx], idx + 1);	break;
				case 1:	dfs(num - arr[idx], idx + 1);	break;
				case 2:	dfs(num * arr[idx], idx + 1);	break;
				case 3:	dfs(num / arr[idx], idx + 1);	break;
 
				}
				// 재귀호출이 종료되면 다시 해당 연산자 개수를 복구한다.
				operator[i]++;
			}
		}
	}
 
}