풀이
시뮬레이션 문제이다. dfs를 사용하여 완전탐색하여 모든 경우를 찾아내고, 그 경우 값을 최댓값과 비교하여 갱신하는 방법을 사용하였다. dfs에 적용된 핵심 알고리즘으로는 현재 dfs에서 괄호를 넣지 않은 경우와 넣은 경우를 계산하여 다음 dfs를 호출하는 것이다.
- 숫자 배열과 연산자 배열에 입력값을 넣는다.
- dfs();
- dfs의 파라미터는 다음과 같다.
- dfs(연산의 합, 이번 dfs에서 진행할 연산, 이번 dfs에서 사용할 수의 배열 인덱스, dfs의 호출 깊이)
- dfs함수 설명
- 호출이 멈춰야할 때는 숫자 배열의 idx가 끝까지 갔을 때 멈춰야 하므로, depth가 숫자 배열의 크기-1이 되었을 때 최댓값을 갱신하며 return 한다.
- 이후로는 경우의 수에 관한 코드이다.
- 괄호를 삽입하는 경우는 각 dfs에서 숫자 배열의 현재 idx+1한 값을 추가로 불러오고, 연산자 또한 현재 연산자의 뒤에 연산자를 가져와서 연산하여 괄호를 삽입한것과 같은 값이 나오도록 하였다.
- 현재 dfs에서 처리해야할 연산자가 +인 경우
- 그 뒤의 연산자가 + 인경우
- 그 뒤의 연산자가 - 인경우
- 그 뒤의 연산자가 * 인경우
- 그 뒤의 연산자가 / 인경우
- 현재 dfs에서 처리해야할 연산자가 +인 경우
- 위 경우의 수를 -, *, /를 반복한다…
결과적으로 괄호 연산을 어떻게 할지!, 그리고 경우의 수가 어떻게 되는지! 만 떠올린다면 노가다 조건문으로 쉽게 풀 수 있는 문제였다.(다행히 쉽게 풀었다)
소스 코드
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
95
96
97
import java.util.*;
import java.io.*;
public class 괄호추가하기 {
static int n;
static int max = Integer.MIN_VALUE;
static int[] num;
static String[] op;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
num = new int[n/2 +1];
op = new String[n/2];
int numIdx = 0;
int opIdx = 0;
String tmp = br.readLine();
for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
num[numIdx] = Integer.parseInt(tmp.substring(i, i+1));
numIdx++;
} else {
op[opIdx] = tmp.substring(i, i+1);
opIdx++;
}
}
dfs(num[0], 0, 1, 0);
System.out.println(max);
}
static void dfs(int sum, int operator, int idx, int depth) {
if (depth == n/2) {
max = Math.max(sum, max);
return;
}
if (op[operator].equals("+")) {
dfs(sum+num[idx], operator+1, idx+1, depth+1);
if (operator+1 <= op.length-1) {
if (op[operator+1].equals("+")) {
dfs(sum+(num[idx]+num[idx+1]), operator+2, idx+2, depth+2);
} else if (op[operator+1].equals("-")) {
dfs(sum+(num[idx]-num[idx+1]), operator+2, idx+2, depth+2);
} else if (op[operator+1].equals("*")) {
dfs(sum+(num[idx]*num[idx+1]), operator+2, idx+2, depth+2);
} else {
dfs(sum+(num[idx]/num[idx+1]), operator+2, idx+2, depth+2);
}
}
} else if (op[operator].equals("-")) {
dfs(sum-num[idx], operator+1, idx+1, depth+1);
if (operator+1 <= op.length-1) {
if (op[operator+1].equals("+")) {
dfs(sum-(num[idx]+num[idx+1]), operator+2, idx+2, depth+2);
} else if (op[operator+1].equals("-")) {
dfs(sum-(num[idx]-num[idx+1]), operator+2, idx+2, depth+2);
} else if (op[operator+1].equals("*")) {
dfs(sum-(num[idx]*num[idx+1]), operator+2, idx+2, depth+2);
} else {
dfs(sum-(num[idx]/num[idx+1]), operator+2, idx+2, depth+2);
}
}
} else if (op[operator].equals("*")) {
dfs(sum*num[idx], operator+1, idx+1, depth+1);
if (operator+1 <= op.length-1) {
if (op[operator+1].equals("+")) {
dfs(sum*(num[idx]+num[idx+1]), operator+2, idx+2, depth+2);
} else if (op[operator+1].equals("-")) {
dfs(sum*(num[idx]-num[idx+1]), operator+2, idx+2, depth+2);
} else if (op[operator+1].equals("*")) {
dfs(sum*(num[idx]*num[idx+1]), operator+2, idx+2, depth+2);
} else {
dfs(sum*(num[idx]/num[idx+1]), operator+2, idx+2, depth+2);
}
}
} else {
dfs(sum/num[idx], operator+1, idx+1, depth+1);
if (operator+1 <= op.length-1) {
if (op[operator+1].equals("+")) {
dfs(sum/(num[idx]+num[idx+1]), operator+2, idx+2, depth+2);
} else if (op[operator+1].equals("-")) {
dfs(sum/(num[idx]-num[idx+1]), operator+2, idx+2, depth+2);
} else if (op[operator+1].equals("*")) {
dfs(sum/(num[idx]*num[idx+1]), operator+2, idx+2, depth+2);
} else {
dfs(sum/(num[idx]/num[idx+1]), operator+2, idx+2, depth+2);
}
}
}
}
}
태클 감사합니다.
조언 환영입니다.