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

• 문제 링크

14888번: 연산자 끼워넣기

 

• 풀이 과정

크기가 n인 number 배열을 생성해 연산할 수를 입력받아 저장하고,

연산자는 크기가 4인 operator 배열에 연산자의 개수를 입력받아 저장하여

해당 배열의 인덱스가 각각의 연산자를 의미하도록 한다. (+ : 0, - : 1, * : 2, / : 3)

 

operator 배열에 존재하는 연산자를 사용하는 모든 연산의 경우의 수를 재귀 함수를 통해 구하고

연산자를 사용할 때마다 해당 연산자의 개수를 1 감소 시킨다.

재귀 호출 종료 시 감소시켰던 연산자를 복구해 또 다른 경우의 수를 이어서 구한다.

 

이렇게 각각의 연산마다 갱신된 최대값, 최소값을 최종적으로 정답으로써 출력한다.

 

• 풀이 코드

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

public class Main {

	static int n;
	static int[] number;
	static int[] operator;
	static int max = Integer.MIN_VALUE;
	static int min = Integer.MAX_VALUE;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		n = Integer.parseInt(br.readLine());
		number = new int[n];
		operator = new int[4];
		
		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());
		
		recursion(number[0], 1);
		
		bw.write(max + "\n" + min + "\n");
		bw.flush();
	}

	private static void recursion(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++) {
			if (operator[i] > 0) {
				operator[i]--;

				if (i == 0)
					recursion(num + number[idx], idx + 1);
				else if (i == 1)
					recursion(num - number[idx], idx + 1);
				else if (i == 2)
					recursion(num * number[idx], idx + 1);
				else
					recursion(num / number[idx], idx + 1);

				operator[i]++;
			}
		}
	}

}