👀 문제
https://www.acmicpc.net/problem/15658
👊 도전
1. 설계
- DFS를 이용하여 +,-,*,/를 사용하는 모든 경우의 수를 확인한 후 max와 min을 설정한다.
2. 구현 (성공 코드)
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
import java.util.Scanner;
/**
* @author HEESOO
*
*/
public class Main {
static int n;
static int[] array, operator;
static int max=Integer.MIN_VALUE;
static int min=Integer.MAX_VALUE;
public static void dfs(int idx, int sum) {
if(idx==n) {
max=Math.max(max, sum);
min=Math.min(min, sum);
return;
}
if(operator[0]>0) {
operator[0]--;
dfs(idx+1, sum+array[idx]);
operator[0]++;
}
if(operator[1]>0) {
operator[1]--;
dfs(idx+1, sum-array[idx]);
operator[1]++;
}
if(operator[2]>0) {
operator[2]--;
dfs(idx+1, sum*array[idx]);
operator[2]++;
}
if(operator[3]>0) {
operator[3]--;
dfs(idx+1, sum/array[idx]);
operator[3]++;
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan = new Scanner(System.in);
n=scan.nextInt();
array=new int[n];
for(int i=0;i<n;i++)
array[i]=scan.nextInt();
operator=new int[4];
for(int i=0;i<4;i++)
operator[i]=scan.nextInt();
dfs(1,array[0]);
System.out.println(max);
System.out.println(min);
}
}
3. 결과
🤟 성공 🤟
4. 설명
- DFS를 이용하여 모든 경우를 구한다
- n개의 숫자와 연산자를 적절히 조합하여 모든 경우를 구한 후 max와 min을 구해야한다.
- dfs()를 재귀호출하는 방식으로 모든 경우를 구한다.
- operator[i]에 값이 있다면 사용한다는 의미로 operator[i]–후 재귀 호출, 호출이 끝난 후에는 다음 사용을 위해 operator[i]++를 해야한다.
- 첫 번째는 연산자의 사용이 필요없으므로 main에서 sum에 바로 넣어 dfs를 호출한다. 또한 첫 번째 숫자를 사용했으므로 idx는 1부터 확인하면 된다.