# 백준 14888번 연산자 끼워넣기

## Solution

import sys

n = int(input())

nums = list(map(int, input().strip().split()))
ops_count = list(map(int, input().strip().split()))
save = [0] * sum(ops_count)
min_v = 1e9
max_v = -1e9

def calculate(prev, i, next):
if i == 0:
return prev + next
if i == 1:
return prev - next
if i == 2:
return prev * next
if i == 3:
if prev < 0:
return -((-prev) // next)
else:
return prev // next

def solve(x, value):
global min_v, max_v
if x == n - 1:
min_v = min(min_v, value)
max_v = max(max_v, value)
return
else:
for cand in range(4):
if ops_count[cand] >= 1:
ops_count[cand] -= 1
result = calculate(value, cand, nums[x + 1])
solve(x + 1, result)
ops_count[cand] += 1

solve(0, nums[0])
print(max_v)
print(min_v)
• 모범 풀이
import sys
min = 1e9
max = -1e9

def calculator(operand1, operator, operand2):
if operator == 0:
return operand1 + operand2
if operator == 1:
return operand1 - operand2
if operator == 2:
return operand1 * operand2
if operator == 3:
if operand1 < 0:
return - ((-operand1) // operand2)
else:
return operand1 // operand2

def rec_func(k, value):
if k == n - 1:
global min, max
min = min if min < value else value
max = max if max > value else value
else:
global operators
for cand in range(4):
if operators[cand] >= 1:
operators[cand] -= 1
rec_func(k + 1, calculator(value, cand, nums[k + 1]))
operators[cand] += 1

rec_func(0, nums[0])
print(max)
print(min)
• java 풀이
import java.io.*;
import java.util.*;

public class Main {
static StringBuilder sb = new StringBuilder();

static void input() {
N = scan.nextInt();
nums = new int[N + 1];
operators = new int[5];
for (int i = 1; i <= N; i++) nums[i] = scan.nextInt();
for (int i = 1; i <= 4; i++) operators[i] = scan.nextInt();

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

static int N, max, min;
static int[] nums, operators;

// 피연산자 2개와 연산자가 주어졌을 때 계산해주는 함수
static int calculator(int operand1, int operator, int operand2){
// value, order[i], num[i+1]
if (operator == 1) // +
return operand1 + operand2;
else if (operator == 2) // -
return operand1 - operand2;
else if (operator == 3) // *
return operand1 * operand2;
else // /
return operand1 / operand2;
}

// order[1...N-1] 에 연산자들이 순서대로 저장될 것이다.
static void rec_func(int k, int value) {
if (k == N) {
// 완성된 식에 맞게 계산을 해서 정답에 갱신하는 작업
max = Math.max(max, value);
min = Math.min(min, value);
} else {
// k 번째 연산자는 무엇을 선택할 것인가?
for (int cand = 1; cand <= 4; cand++){
if (operators[cand] >= 1){
operators[cand]--;
rec_func(k + 1, calculator(value, cand, nums[k + 1]));
operators[cand]++;
}
}
}
}

public static void main(String[] args) {
input();
// 1 번째 원소부터 M 번째 원소를 조건에 맞게 고르는 모든 방법을 탐색해줘
rec_func(1, nums[1]);
sb.append(max).append('\n').append(min);
System.out.println(sb.toString());
}

StringTokenizer st;

}

public FastReader(String s) throws FileNotFoundException {
}

String next() {
while (st == null || !st.hasMoreElements()) {
try {
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}

int nextInt() {
return Integer.parseInt(next());
}

long nextLong() {
return Long.parseLong(next());
}

double nextDouble() {
return Double.parseDouble(next());
}

String nextLine() {
String str = "";
try {
}