14888번 : 연산자 끼워넣기 [Java]

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

14888번: 연산자 끼워넣기

 

풀이방법

가장 큰 값과 가장 작은 값을 찾기 위해선 모든 연산자를 대입하며 전체 경우를 다 확인해야 한다.

 

연산자 배열을 돌며 연산자가 1개 이상인 경우 연산자를 사용하고 재귀를 호출한다.

재귀를 호출할 때 연산자의 값을 1 감소시키고 재귀 호출이 종료되면 연산자의 값을 다시 돌려놓는다.

 

모든 숫자를 다 사용했다면 최댓값과 최솟값을 저장한다.

 

 

전체 코드

import java.util.Scanner;

public class Main {
	static int N;
	static int[] num, op;
	static int Max = Integer.MIN_VALUE;
	static int Min = Integer.MAX_VALUE;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt(); // 수의 개수

		num = new int[N];
		for (int i = 0; i < N; i++)
			num[i] = sc.nextInt();

		op = new int[4]; // 연산자배열 : +, -, *, /
		for (int i = 0; i < 4; i++)
			op[i] = sc.nextInt();

		dfs(num[0], 1);

		System.out.println(Max);
		System.out.println(Min);

	}

	private static void dfs(int n, int idx) {
		if (idx == N) {
			Max = Math.max(Max, n);
			Min = Math.min(Min, n);
			return;
		}

		for (int i = 0; i < 4; i++) {
			if (op[i] > 0) { // 해당 연산자 사용 가능

				op[i]--;

				switch (i) {
				case 0: // 더하기
					dfs(n + num[idx], idx + 1);
					break;
				case 1: // 빼기
					dfs(n - num[idx], idx + 1);
					break;
				case 2: // 곱하기
					dfs(n * num[idx], idx + 1);
					break;
				case 3: // 나누기
					dfs(n / num[idx], idx + 1);
					break;
				}

				op[i]++;
			}
		}

	}
}