import java.io.*;
import java.util.*;
public class Main {
static BufferedReader br;
static int N;
static int[] A;
static char[] operators;
static int plus, minus, multiply, divide;
static int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
static int sum = 0;
public static void input() throws IOException {
br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
A = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
st = new StringTokenizer(br.readLine());
plus = Integer.parseInt(st.nextToken());
minus = Integer.parseInt(st.nextToken());
multiply = Integer.parseInt(st.nextToken());
divide = Integer.parseInt(st.nextToken());
operators = new char[plus+minus+multiply+divide];
int cnt = 0;
for(int i = 0; i < plus; i++) {
operators[cnt++] = '+';
}
for(int i = 0; i < minus; i++) {
operators[cnt++] = '-';
}
for(int i = 0; i < multiply; i++) {
operators[cnt++] = '*';
}
for(int i = 0; i < divide; i++) {
operators[cnt++] = '/';
}
}
public static void solve(char[] operators, int depth) {
if(depth == N-1) {
calculate(operators);
max = Math.max(max, sum);
min = Math.min(min, sum);
sum = 0;
}
for(int i = depth; i < N-1; i++) {
swap(operators, i, depth);
solve(operators, depth+1);
swap(operators, i, depth);
}
}
public static void calculate(char[] operators) {
sum += A[0];
for(int i = 0; i < N-1; i++) {
if(operators[i] == '+') {
sum += A[i+1];
}
if(operators[i] == '-') {
sum -= A[i+1];
}
if(operators[i] == '*') {
sum *= A[i+1];
}
if(operators[i] == '/') {
sum /= A[i+1];
}
}
}
public static void swap(char[] operators, int x, int y) {
char tmp = operators[x];
operators[x] = operators[y];
operators[y] = tmp;
}
public static void main(String[] args) throws IOException {
input();
solve(operators, 0);
System.out.println(max);
System.out.println(min);
}
}
완전탐색 문제로 나열된 연산자들의 모든 경우의 수를 찾는것이 키포인트였다.
1. operators 배열을 생성, 연산자 초기화 작업 ( input() )
2. operators 순서에 따라 계산작업 후 max, min 판별 ( calculate() )
3. 2의 작업을 operators 배열의 모든 경우의 수를 구할 때 까지 반복 ( solve() )
'Dev > PS' 카테고리의 다른 글
[백준] 1107 리모컨 java (0) | 2022.02.22 |
---|---|
[백준] 2661 좋은수열 java (0) | 2022.02.10 |
[백준] 14889 스타트와 링크 java (0) | 2022.02.08 |
[백준] 10819 차이를 최대로 java (0) | 2022.02.07 |
[백준] 1186 부분수열의 합 java (0) | 2022.02.02 |