[BaekJoon] 14888 연산자 끼워넣기

1.  문제 링크

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

2.  문제

요약

• N개의 수로 이루어진 수열 $A_1$, $A_2$, ..., $A_N$이 주어지고 수 사이에 끼워넣을 수 있는 N - 1개의 연산자가 주어집니다.
• 연산자는 덧셈, 뺄셈, 곱셈, 나눗셈으로만 이루어져 있습니다.
• 주어진 수의 순서를 바꾸지 않고 수 사이에 연산자를 하나씩 넣어 수식들을 만들 수 있는데, 각 수식은 연산자 우선 순위를 무시하고 앞에서부터 계산을 진행합니다.
• 나눗셈은 정수 나눗셈으로서 몫만 취합니다. 또한 음수를 양수로 나눌 때는 음수를 양수로 바꾼 뒤 몫을 취하고 그 몫을 음수로 바꿉니다.
• N개의 수와 N - 1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 문제입니다.
• 입력: 첫 번째 줄에 2보다 크거나 같고 11보다 작거나 같은 수의 개수 N이 주어지고 두 번째 줄에 1보다 크거나 같고 100보다 작거나 같은 $A_1$, $A_2$, ..., $A_N$이 주어지며 세 번째 줄에 합이 N - 1인 4개의 정수가 주어지는데, 이는 차례대로 덧셈의 개수, 뺄셈의 개수, 곱셈의 개수, 나눗셈의 개수입니다.
• 출력: 첫 번째 줄에 식의 결과의 최댓값을, 두 번째 줄에 식의 결과의 최솟값을 출력합니다.
  • 식의 결과가 -10억보다 크거나 같고 10억보다 작거나 같은 입력들만 주어지고 중간에 계산되는 식의 결과 또한 항상 -10억보다 크거나 같고 10억보다 작거나 같다.

3.  소스코드

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

public class Main {
	static int[] nums;
	static int[] operators;
	static int max = Integer.MIN_VALUE;
	static int min = Integer.MAX_VALUE;
	static int n;
	public void getMinMax(int num, int index) {
		if(index == n) {
			max = Math.max(max, num);
			min = Math.min(min, num);
			return;
		}
		for(int i = 0; i < 4; i++) {
			if(operators[i] > 0) {
				operators[i]--;
				switch(i) {
				case 0:
					getMinMax(num + nums[index], index + 1);
					break;
				case 1:
					getMinMax(num - nums[index], index + 1);
					break;
				case 2:
					getMinMax(num * nums[index], index + 1);
					break;
				case 3:
					getMinMax(num / nums[index], index + 1);
					break;
				}
				operators[i]++;
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		n = Integer.parseInt(br.readLine());
		nums = new int[n];
		String[] input = br.readLine().split(" ");
		for(int i = 0; i < n; i++) {
			nums[i] = Integer.parseInt(input[i]);
		}
		operators = new int[4];
		input = br.readLine().split(" ");
		for(int i = 0; i < 4; i++) {
			operators[i] = Integer.parseInt(input[i]);
		}
		Main m = new Main();
		m.getMinMax(nums[0], 1);
		bw.write(max + "\n" + min + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제는 백트래킹을 이용하여 해결할 수 있습니다.
• 주어진 연산자들의 개수를 배열에 넣어 재귀호출을 통해 수 사이에 연산자를 넣어주어 그 때의 값을 계산하고 해당 연산자의 개수를 1씩 감소시키며 해당 연산자의 개수가 0이 된다면 다음 연산자로 넘어가고 이러한 행동을 반복하여 하나의 식의 값을 계산합니다.
• 하나의 식이 완성됐다면 이전으로 돌아가 연산자의 개수를 1 늘려 또 다른 식을 만들고 연산합니다.
• 이러한 방식으로 모든 식을 만들어 계산해보고 그 중 최대값과 최소값을 찾아 이를 출력합니다.

public void getMinMax(int num, int index) {
	if(index == n) {
		max = Math.max(max, num);
		min = Math.min(min, num);
		return;
	}
	for(int i = 0; i < 4; i++) {
		if(operators[i] > 0) {
			operators[i]--;
			switch(i) {
			case 0:
				getMinMax(num + nums[index], index + 1);
				break;
			case 1:
				getMinMax(num - nums[index], index + 1);
				break;
			case 2:
				getMinMax(num * nums[index], index + 1);
				break;
			case 3:
				getMinMax(num / nums[index], index + 1);
				break;
			}
			operators[i]++;
		}
	}
}

1. 주어진 수열의 수들을 배열 nums에 넣어주고 주어진 연산자의 개수를 배열 operators에 넣어줍니다. 이 때, index 0는 덧셈, index 1은 뺄셈, index 2는 곱셈, index 3은 나눗셈을 의미합니다.
2. 첫 번째 수부터 시작하여 수 사이에 연산자를 넣어 식들을 생성하고 해당 식들의 값을 계산하며 최솟값과 최댓값을 찾습니다.
   1. 만약 연산자 N - 1개를 모두 사용하여 식을 완성했다면 최댓값을 의미하는 변수인 max에 현재 max의 값과 완성된 식의 값 중 더 큰 값을 넣어주고 최솟값을 의미하는 변수인 min에 현재 min의 값과 완성된 식의 값 중 더 작은 값을 넣어줍니다.
   2. 그렇지 않다면 연산자를 덧셈부터 시작하여 반복문을 돌면서 식을 생성하고 해당 식의 값을 생성합니다.
      1. 만약 해당 연산자의 개수가 0이 아니라면 해당 연산자의 개수를 1 줄여줍니다.
      2. 해당 연산자에 맞는 연산을 현재까지 계산한 수와 그 다음 수에 대해 진행하고 계산된 값과 다음 수의 index를 인자로 하여 재귀함수를 호출합니다.
      3. 만약 식이 완성되었다면 해당 연산자의 개수를 1 증가시키고 다른 식을 생성합니다.
3. 2번을 통해 최솟값과 최댓값을 찾았으니 이를 출력합니다.