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

문제

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

풀이

• N개의 수로 이루어진 수열이 주어진다.
• 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다.
  • 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.
• 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다.
  • 이때, 주어진 수의 순서를 바꾸면 안 된다.
• 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다.
• 나눗셈은 정수 나눗셈으로 몫만 취한다.
  • 음수를 양수로 나눌 때는 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다.
• N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

N개의 수와 N-1개의 연산자를 이용해 최댓값과 최솟값을 구해야 하는 문제입니다.
숫자의 위치는 고정시키고 연산자의 순서만 바꿔넣어 주면 되죠.
연산자를 사용할 수 있는 모든 순열을 구하여 최댓값과 최솟값을 갱신하면 됩니다.

입력

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine()); // 수의 개수

		// 수열 초기화 및 할당
		StringTokenizer st = new StringTokenizer(br.readLine());
		nums = new int[n];
		for (int i = 0; i < n; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}

		// 연산자 할당
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < 4; i++) {
			oper[i] = Integer.parseInt(st.nextToken());
		}

• n: 수의 개수
• nums: n개의 수를 갖고 있는 수열
• oper: 덧셈, 뺄셈, 곱셈, 나눗셈 연산자를 저장할 배열

연산자 순열

	private static void dfs(int depth, int result) {
		if (depth == n) { // n개의 수를 뽑았을 경우 (기저조건)
        	// 최댓값, 최솟값 갱신
			max = Math.max(max, result);
			min = Math.min(min, result);
			return;
		}

		// 4개의 연산자 사용
		for (int i = 0; i < 4; i++) {
			if (oper[i] > 0) { // 만약 연산자의 개수가 0개가 아니라면
				--oper[i]; // 사용처리

				switch (i) {
				case 0: // 덧셈
					dfs(depth + 1, result + nums[depth]);
					break;
				case 1: // 뺄셈
					dfs(depth + 1, result - nums[depth]);
					break;
				case 2: // 곱셈
					dfs(depth + 1, result * nums[depth]);
					break;
				case 3: // 나눗셈
					if (result < 0) // 앞 숫자가 음수일 경우
						dfs(depth + 1, -(-result / nums[depth]));
					else // 앞 숫자가 양수일 경우
						dfs(depth + 1, result / nums[depth]);
					break;
				}

				++oper[i]; // 사용한 값 원복 (백트래킹)
			}
		}
	}

• depth: 사용한 숫자 및 수열의 인덱스 판별
• result: 현재까지 계산한 결과
• 4개의 연산자를 사용할 건데, 이 중 남아있는 연산자의 개수가 1개 이상이라면 이를 사용하여 연산을 하고 재귀해 줍니다.
• 사용하기 편하게 하기 위해 switch문을 사용하였습니다.
• 음수를 양수로 나눌 땐 이를 양수로 바꾼 후 계산합니다.
  후에 이 몫을 음수로 바꾸어 줘야 합니다.(문제 조건)
• 연산이 끝난 후에는 이 연산 횟수를 다시 원래대로 돌려 줍니다. (백트래킹)

이렇게 하면 갖고 있는 연산자를 모두 이용해서 답을 찾을 수 있습니다.

실행 및 출력

		max = Integer.MIN_VALUE;
		min = Integer.MAX_VALUE;

		dfs(1, nums[0]);

		System.out.println(max);
		System.out.println(min);

• max: 최댓값
• min: 최솟값
• dfs: depth를 1부터 실행하는 이유는 첫 번째 수는 항상 입력 받은 수로 고정이기 때문입니다.
  때문에, 항상 1번 인덱스 값부터 연산을 시작합니다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, max, min;
	static int[] nums;
	static int[] oper = new int[4]; // +, -, *, /

	private static void dfs(int depth, int result) {
		if (depth == n) {
			max = Math.max(max, result);
			min = Math.min(min, result);
			return;
		}

		for (int i = 0; i < 4; i++) {
			if (oper[i] > 0) {
				--oper[i];

				switch (i) {
				case 0:
					dfs(depth + 1, result + nums[depth]);
					break;
				case 1:
					dfs(depth + 1, result - nums[depth]);
					break;
				case 2:
					dfs(depth + 1, result * nums[depth]);
					break;
				case 3:
					if (result < 0)
						dfs(depth + 1, -(-result / nums[depth]));
					else
						dfs(depth + 1, result / nums[depth]);
					break;
				}

				++oper[i];
			}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());

		StringTokenizer st = new StringTokenizer(br.readLine());
		nums = new int[n];
		for (int i = 0; i < n; i++) {
			nums[i] = Integer.parseInt(st.nextToken());
		}

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < 4; i++) {
			oper[i] = Integer.parseInt(st.nextToken());
		}

		max = Integer.MIN_VALUE;
		min = Integer.MAX_VALUE;

		dfs(1, nums[0]);

		System.out.println(max);
		System.out.println(min);
	}

}