BOJ 16637 괄호 추가하기
https://www.acmicpc.net/problem/16637
문제
길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순서대로 계산해야 한다. 예를 들어, 3+8×7-9×2의 결과는 136이다.
수식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산해야 한다. 단, 괄호 안에는 연산자가 하나만 들어 있어야 한다. 예를 들어, 3+8×7-9×2에 괄호를 3+(8×7)-(9×2)와 같이 추가했으면, 식의 결과는 41이 된다. 하지만, 중첩된 괄호는 사용할 수 없다. 즉, 3+((8×7)-9)×2, 3+((8×7)-(9×2))은 모두 괄호 안에 괄호가 있기 때문에, 올바른 식이 아니다.
수식이 주어졌을 때, 괄호를 적절히 추가해 만들 수 있는 식의 결과의 최댓값을 구하는 프로그램을 작성하시오. 추가하는 괄호 개수의 제한은 없으며, 추가하지 않아도 된다.
입력
첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 번갈아가면서 나온다. 연산자는 +, -, * 중 하나이다. 여기서 *는 곱하기 연산을 나타내는 × 연산이다. 항상 올바른 수식만 주어지기 때문에, N은 홀수이다.
출력
첫째 줄에 괄호를 적절히 추가해서 얻을 수 있는 결과의 최댓값을 출력한다. 정답은 $2^{31}$보다 작고, $-2^{31}$보다 크다.
예제 입력 1
9 3+8*7-9*2
예제 출력 1
136
예제 입력 2
5 8*3+5
예제 출력 2
64
… 이하 예제 생략
코드
문제의 제목에서 괄호가 등장해서 처음에는 분명 스택 문제일 것 같다고 생각했다.
하지만 문제에서 ‘중첩된 괄호가 없다’는 내용이 나왔는데, 이 부분에서 스택 문제가 아닌 것을 알 수 있다.
이번 문제는 단순히 계산을 우선할 연산자를 골라 최대 결과를 만들어 내는 문제였다.
브루트포스로 풀 수 있었고, 우선 계산할 연산자를 선택하는 과정에서 boolean 배열을 사용하지 않고, 비트마스킹을 사용했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int maxValue = Integer.MIN_VALUE;
static char[] operations;
static int[] numbers;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
operations = new char[N / 2];
numbers = new int[N - operations.length];
// 숫자와 연산자를 분리해서 저장
for (int i = 0; i < N; i++) {
if((i & 1) == 0) {
numbers[i / 2] = br.read() - '0';
} else {
operations[i / 2] = (char) br.read();
}
}
searchMaxValue(0, 0);
System.out.println(maxValue);
}
/**
* 우선 계산할 연산자를 브루트포스로 선택해서 그 결과 중 최댓값을 고르는 메소드
* @param operationIndex 우선 계산할지 선택 중인 연산자의 인덱스
* @param selected 선택한 연산자들을 표현한 비트마스크
*/
static void searchMaxValue(int operationIndex, int selected) {
// 우선 계산할 연산자를 모두 고른 경우의 결과가 최대값인지 검사
if(operationIndex >= operations.length) {
int value = calculateValue(selected);
maxValue = Integer.max(maxValue, value);
return;
}
// 현재 연산자 선택 안함
searchMaxValue(operationIndex + 1, selected);
// 현재 연산자 선택함 (괄호가 중첩될 수 없어서 다음 연산자는 우선 계산을 할 수 없으므로 다다음 연산자 탐색)
searchMaxValue(operationIndex + 2, selected | 1 << operationIndex);
}
/**
* 우선 계산할 연산자에 따른 전체 연산 결과를 반환하는 메소드
* @param selected 우선 계산할 연산자들을 표현한 비트마스크
* @return 전체 연산 결과
*/
static int calculateValue(int selected) {
int[] savedNumbers = numbers.clone();
// 우선 계산할 연산자들을 먼저 계산한 후, 계산 결과를 savedNumbers 배열에 저장
for (int i = 0; i < operations.length; i++) {
if((selected & 1 << i) != 0) {
savedNumbers[i] = executeOperation(savedNumbers[i], savedNumbers[i + 1], operations[i]);
}
}
int value = savedNumbers[0]; // 연산 결과
// 연산자들을 순차적으로 순회하며 계산
for (int i = 0; i < operations.length; i++) {
// 계산할 연산자가 우선 계산된 연산자일 경우, 계산 스킵
if((selected & 1 << i) != 0) {
continue;
}
value = executeOperation(value, savedNumbers[i + 1], operations[i]);
}
return value;
}
/**
* 연산자의 종류에 따라 연산 결과를 반환하는 메소드
* @param number1 피연산자1
* @param number2 피연산자2
* @param operation 연산자
* @return 연산 결과
*/
static int executeOperation(int number1, int number2, char operation) {
switch (operation) {
case '+': return number1 + number2;
case '-': return number1 - number2;
default: return number1 * number2;
}
}
}