N개의 수와 N - 1개의 연산자들이 있다.
연산 순서는 고려하지않으며, 모든 연산결과에 대한 최댓값과 최솟값을 구하는 문제이다.
- 모든 결과를 고려하는 백트래킹 문제이다. 연산 순서는 고려하지않아 편하며, depth가 N에 도달했을때 결과들을 Math.max, Math.min으로 비교해나가며 백트래킹한다.
- 다만 마음에 걸리는 점은, 무엇을 visited 배열 대용으로 잡아야하느냐이다. 그래서 opeartorNum의 수를 점점 줄여나가는 방향으로 잡기로했다.
package backTracking;
import java.io.*;
import java.util.StringTokenizer;
import static java.lang.Math.*;
public class OperatorAdd {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
int[] num = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
num[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
int[] operatorNum = new int[4]; // arr
for (int i = 0; i < 4; i++) {
operatorNum[i] = Integer.parseInt(st.nextToken());
}
// 만들수있는 최댓값, 최솟값
// 나눗셈의 경우 : 몫만 취한다. 음수일 경우: 양수로 바꾼후 -> 몫을 취하고 -> 음수로 다시 바꾼다.
// 연산자는 개수가 N - 1개
// 경우의 수를 모두 구한다.
// N = 6 -> 5개. 1 2 3 4 5 -> 경우의 수 5! / (같은거)!
int depth = 1;
max = -1000000000;
min = 1000000000;
int sum = num[0];
DFS(num, operatorNum, sum, N, depth);
bw.write(String.valueOf(max) + "\n" + String.valueOf(min));
bw.flush();
br.close();
bw.close();
}
private static int max;
private static int min;
private static void DFS(int[] num, int[] operatorNum, int sum, int N, int depth) {
if (depth == N) {
max = max(max, sum);
min = min(min, sum);
return;
}
for (int i = 0; i < 4; i++) {
if (operatorNum[i] > 0) {
operatorNum[i]--; // 먼저 카운트 뺌.
if (i == 0) {
// 함수 인자에 sum + num[depth] 형태로 넣는다. 그래야 빠져나올때 이전 결과로 돌아옴.
// 먼저 더하고 넣어버리면 결과가 그대로 남는다.
DFS(num, operatorNum, sum + num[depth], N,depth + 1);
}
else if (i == 1) {
DFS(num, operatorNum, sum - num[depth], N,depth + 1);
}
else if (i == 2) {
DFS(num, operatorNum, sum * num[depth], N,depth + 1);
}
else {
DFS(num, operatorNum, sum / num[depth], N, depth + 1);
}
operatorNum[i]++; // 카운트 나중에 더함
}
}
}
}
- 여기서 재미있는점은 C++ 나눗셈 계산을 고려하라고 적혀있는데, 사실 java에선 자동으로 계산되는 별의미없는 말이였다.
- 또한, DFS 인자에 sum + num[depth]같은 계산을 해주어야하는데, 이는 재귀문이 다시 돌아올때 이전 계산결과로 복귀 되어야하기 때문이다. 미리 sum += num[depth]를 넣은후, 인자로 sum을 대입하면, 마지막 복귀때 이전 계산결과가 그대로 남아버렸다.