제출 코드
- 사용 알고리즘 :
부분집합
- 괄호가 중첩되어 들어가지 않는다는 특성을 사용하여, 전체 연산자에서 괄호를 씌워 먼저 계산할 부분을 고르는 모든 가짓수(부분집합)에 대해 연산을 모두 해주었다.
- 기존 부분집합을 구하는 방법과의 차이점은, 이 연산은 괄호가 중첩될 수 없기에 i번째 연산을 하고 나면 i+1번째 연산자는 연산을 하면 안된다는 점이다.
- ((a + b ) + c)가 안됨
1 2 3 4
visit[start] = true; peak(start+2); // 괄호를 씌워 연산을 한 경우, 다다음 연산자부터 검사 visit[start] = false; peak(start+1); // 괄호를 씌우지 않고 넘어간 경우, 다음 연산자부터 검사
- ((a + b ) + c)가 안됨
- 문자열에서 정수형으로 바꿔 계산했다가 다시 문자열로 저장하는 과정이 좀 번거로운것 같다
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
package gold;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class G16637_addBracket {
static int N;
static long max = Long.MIN_VALUE;
static boolean[] visit;
static String[] str;
/* 부분집합을 변형하여 괄호를 칠 수 있는 모든 경우에 대하여 연산 시행
* - start : 해당 연산자의 인덱스
*/
static void peak(int start) {
if(start>=N/2) { // 괄호를 씌울 연산자들을 모두 고른 경우
String[] tmp = new String[N];
for(int i=0; i<N-1; i+=2) {
if(visit[i/2]) { // 괄호칠 부분 -> 연산 결과를 넣어둔다
tmp[i] = calc(i+1, Long.parseLong(str[i]), str)+"";
tmp[i+1] = "";
tmp[i+2] = "";
}else { // 괄호치지 않을 부분 -> 그대로 넣는다
tmp[i] = tmp[i]==null ? str[i] : ""; //
tmp[i+1] = str[i+1];
}
}
if(tmp[N-1]==null) tmp[N-1] = str[N-1]; // 맨 마지막 수
long result = Long.parseLong(tmp[0]);
for(int i=1; i<N; i+=2) { // 괄호친 부분들이 모두 계산되었고, 이제 앞에서부터 순서대로 계산시작
if(tmp[i].equals("")) continue;
result = calc(i, result, tmp);
}
max = Math.max(max, result);
return;
}
// 부분집합 만드는 부분
visit[start] = true;
peak(start+2);
visit[start] = false;
peak(start+1);
}
/* String으로 주어진 연산자를 계산하는 메서드
* i : 연산자가 저장된 인덱스
* pre : 연산자의 전위 값
* arr : 연산자의 후위 값을 가져올 배열
*/
static long calc(int i, long pre, String[] arr) {
switch(str[i]){
case "+":
return pre + Long.parseLong(arr[i+1]);
case "-":
return pre - Long.parseLong(arr[i+1]);
case "*":
return pre * Long.parseLong(arr[i+1]);
}
return -1;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
char[] ch = br.readLine().toCharArray();
String s = "";
str = new String[N];
int idx = 0;
for(char c : ch) {
if(c=='+' || c=='-' || c=='*') {
str[idx] = s;
str[++idx] = c+"";
idx++;
s = "";
}else {
s += c;
}
}
str[N-1] = s;
visit = new boolean[N/2];
peak(0);
System.out.println(max);
}
}