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

문제

 

 

접근 방식

수가 최대 11개까지만 있어서 무식하게 풀어도 가능한

기본적인 백트래킹 문제다.

 

간단한 과정은 다음과 같다.

1. 각 연산자의 사용횟수가 아직 남아있는지 확인
2. 남아있다면 사용횟수를 1 감소시킨 후 재귀호출
3. 자기 자신으로 돌아오면 감소시킨 사용횟수 복구
4. 식을 모두 사용했으면 현재 값을 비교해 최대최소 기록

 

풀이

public class Main {

	static int n, plus, minus, multi, div;
	static int min = 1000000001, max = -1000000001;
	static int[] arr;
	static boolean[] isUsed;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		n = Integer.parseInt(br.readLine());
		arr = new int[n];
		isUsed = new boolean[n];

		StringTokenizer st = new StringTokenizer(br.readLine());

		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		st = new StringTokenizer(br.readLine());

		plus = Integer.parseInt(st.nextToken());
		minus = Integer.parseInt(st.nextToken());
		multi = Integer.parseInt(st.nextToken());
		div = Integer.parseInt(st.nextToken());

		solve(arr[0], 2);

		sb.append(max).append("\n").append(min);

		System.out.println(sb);
	}

	static void solve(int result, int cur) {
		if(cur > n) {
			min = Math.min(min, result);
			max = Math.max(max, result);
			return;
		}

		if (plus != 0) {
			plus--;
			solve(result + arr[cur - 1], cur + 1);
			plus++;
		}

		if (minus != 0) {
			minus--;
			solve(result - arr[cur - 1], cur + 1);
			minus++;
		}

		if (multi != 0) {
			multi--;
			solve(result * arr[cur - 1], cur + 1);
			multi++;
		}

		if (div != 0) {
			div--;
			solve(result / arr[cur - 1], cur + 1);
			div++;
		}

	}
}