[BOJ] 연산자끼워넣기
문제
N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.
우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.
예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.
1+2+3-4×5÷6
1÷2+3+4-5×6
1+2÷3×4-5+6
1÷2×3-4+5+6
식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.1+2+3-4×5÷6 = 1
1÷2+3+4-5×6 = 12
1+2÷3×4-5+6 = 5
1÷2×3-4+5+6 = 7
N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.
풀이
최소, 최댓값을 구하려면 결국에는 모든 경우를 탐색해야 한다.
사용했던 연산자들의 횟수와 위치를 변경해가며 구해야 하므로 조합과 유사한 구조인 백트래킹을 이용하여 구현해야 한다고 생각하였다.
연산의 결과인 sum에 대하여 각 연산자에 대해서 갯수가 0이 아닌 연산자에 대해 +, -, *,/을 계산해 준 후,
연산 끝에 다다르면 Max,와 Min을 구하여 이를 저장하도록 하였다.
백트래킹은 문제를 볼 수록 구현하기가 조금 까다로운 것 같다.ㅜ
역시 많이 풀어보는 수 밖에 없는 것 같다.
import java.util.*;
import java.lang.*;
import java.io.*;
class Main {
static int[] operator;
static int[] numbers;
static int max = Integer.MIN_VALUE;
static int min = Integer.MAX_VALUE;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
operator = new int[4];
int N = Integer.parseInt(br.readLine());
String[] str = br.readLine().split(" ");
numbers = new int[N];
for(int i = 0; i < N; i++) {
numbers[i] = Integer.parseInt(str[i]);
}
str = br.readLine().split(" ");
for(int i = 0; i < 4; i++) {
operator[i] = Integer.parseInt(str[i]);
}
trace(numbers[0], 1);
System.out.println(max);
System.out.println(min);
}
static void trace(int sum, int numberIndex) {
if (numberIndex == numbers.length) {
max = Math.max(max, sum);
min = Math.min(min, sum);
return;
}
for(int i = 0; i < 4; i++) {
if (operator[i] > 0) {
operator[i]--;
if (i == 0) {
trace(sum + numbers[numberIndex], numberIndex + 1);
} else if (i == 1) {
trace(sum - numbers[numberIndex], numberIndex + 1);
} else if (i == 2) {
trace(sum * numbers[numberIndex], numberIndex + 1);
} else {
trace(sum / numbers[numberIndex], numberIndex + 1);
}
operator[i]++;
}
}
}
}