-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathDFS : 연산자 끼워 넣기
75 lines (56 loc) · 1.3 KB
/
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
# 문제
- [연산자 끼워 넣기 : 이것이 코딩테스트다 p.349]
# 내용
- 수와 수 사이에 연산자 결정을 완전탐색으로 모든 경우에 대하여 최대값 및 최소값을 구하면 된다.
# 문제 풀이
```java
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
private static int add = 2;
private static int sub = 1;
private static int mul = 1;
private static int div = 1;
private static int N = 0;
private static ArrayList<Integer> arr = new ArrayList<>();
private static int max = Integer.MIN_VALUE;
private static int min = Integer.MAX_VALUE;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
for (int i = 0; i < N; i++) {
arr.add(sc.nextInt());
}
dfs(1, arr.get(0));
System.out.println(max);
System.out.println(min);
}
public static void dfs(int i, int sum) {
if (i == N) {
max = Math.max(max, sum);
min = Math.min(min, sum);
return;
}
if (add > 0) {
add -= 1;
dfs(i + 1, sum + arr.get(i));
add += 1;
}
if (sub > 0) {
sub -= 1;
dfs(i + 1, sum - arr.get(i));
sub += 1;
}
if (mul > 0) {
mul -= 1;
dfs(i + 1, sum * arr.get(i));
mul += 1;
}
if (div > 0) {
div -= 1;
dfs(i + 1, sum / arr.get(i));
div += 1;
}
}
}
```