728x90
문제
15659번: 연산자 끼워넣기 (3)
첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수,
www.acmicpc.net
접근 방식
기존의 연산자 끼워넣기 1, 2번 시리즈와 비슷하지만 연산자의 우선순위를 적용해야 해서
선택한 연산자들을 배열에 기록해 두었다 나중에 한 번에 연산을 해줘야 한다.
중간중간에 처리해서 빠르게 계산을 해보려 했는데 예제들은 통과가 되지만
제출하면 도무지 1 퍼에서 올라가질 않길래 포기하고 한 번에 연산을 해줬다.
기존 방식대로 각각의 연산자들을 선택할 수 있을 때 선택하는 방식으로 진행하면서
n-1개의 연산자를 선택했을 때 스택을 활용해서 우선순위대로 처리해 주면 된다.
덧셈과 뺄셈은 스택에 계속해서 쌓아두다가
곱셈과 나눗셈일 때 이전 값을 꺼내서 계산한 후에 스택에 결과를 넣어주고
모든 연산자를 다 처리한 후에 스택의 값들을 모두 꺼내면서 더해주면 된다.
풀이
public class Main {
static int n, plus, minus, multi, div, max = -1000000001, min = 1000000001;
static int[] arr;
static char[] ops;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
arr = new int[n];
ops = new char[n - 1];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) arr[i] = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
plus = Integer.parseInt(st.nextToken());
minus = Integer.parseInt(st.nextToken());
multi = Integer.parseInt(st.nextToken());
div = Integer.parseInt(st.nextToken());
solve(0);
System.out.println(max + "\n" + min);
}
static void solve(int size) {
if (size == n) {
calcurate();
return;
}
if (size == 0) {
solve(size + 1);
} else {
if (plus != 0) {
plus--;
ops[size - 1] = '+';
solve(size + 1);
plus++;
}
if (minus != 0) {
minus--;
ops[size - 1] = '-';
solve(size + 1);
minus++;
}
if (multi != 0) {
multi--;
ops[size - 1] = '*';
solve(size + 1);
multi++;
}
if (div != 0) {
div--;
ops[size - 1] = '/';
solve(size + 1);
div++;
}
}
}
static void calcurate() {
int result = 0;
Stack<Integer> s = new Stack<>();
s.push(arr[0]);
for (int i = 0; i < n - 1; i++) {
switch (ops[i]) {
case '+': {
s.push(arr[i + 1]);
break;
}
case '-': {
s.push(arr[i + 1] * -1);
break;
}
case '*': {
s.push(s.pop() * arr[i + 1]);
break;
}
default: {
s.push(s.pop() / arr[i + 1]);
break;
}
}
}
while (!s.isEmpty()) {
result += s.pop();
}
max = Math.max(max, result);
min = Math.min(min, result);
}
}
'Java > Algorithms' 카테고리의 다른 글
| [백준] 16946번 : 벽 부수고 이동하기 4 (0) | 2024.04.15 |
|---|---|
| [백준] 2239번 : 스도쿠 (0) | 2024.04.13 |
| [백준] 1759번 : 암호 만들기 (0) | 2024.04.11 |
| [백준] 15658번 : 연산자 끼워넣기 (2) (0) | 2024.04.10 |
| [백준] 2529번 : 부등호 (0) | 2024.04.09 |